Data Structure: Tree - swchen1234/Algorithm GitHub Wiki

Data Structure: Tree

基本概念：

图和树的区别在于图中有环 => 图需要用hashmap 记录已经访问过的点
Tree 的二要素：
- n个点， n-1条边
- 所有点连通
BST
- 左子树中的值 < 根结点的值 < 右子树中的值

九章考察形态归类：

第一类 - 二叉树上求值，求路径 Maximum / Minimum / Average / Sum / Paths
第二类 - 二叉树结构变化
第二类 - 二叉搜索树 Binary Search Tree 从定义出发： • 左子树都比根节点小 • 右子树都不小于根节点

Tree is a special type of graphs, so the two usual techniques used to traverse a graph(DFS & BFS) are also applicable to trees.

BFS 的实现： queue

DFS 的实现：

Iteratively

Iteratively 的实现只考几类题， 其中包括BinaryTree的InOrder/PreOrder Traverse.

必备算法：Interative 版本的tree traversal Iteratively 的实现只考几类题，其中包括BinaryTree的InOrder/PreOrder Traverse
inOrderTraverse

def inOrderTraverse(root):
    stk, res = [], []
    curr = root;
    while(curr || not stk.empty()):
        while(curr):
            stk.push(curr) 
            curr = curr.left
        curr = stk.pop()
        res.append(curr.val) // 只处理从stack pop出来的元素
        curr = curr.right
    return res;

Pre-order Traversal

def preOrderTraverse(root):
    stk, res = [], []
    if(not root):
        return res
    res.push(root);
    while(not stk.empty()){
        curr = stk.pop()
        res.append(curr)
        if(curr.right):
            stk.push(curr.right)
        if(curr.left):
            stk.push(curr.left)
    }
    return res

Recurisively

1. Traverse( top -> down)
2. DivideConquer( bottom -> up)

Tricks:

Use dummy node to hold the head of each level.
It is better to use treeNote *prev as the starting previous node, instead of INT_MIN, INT_MAX, otherwise, you will easily ends up writing long code fixing bugs.

常见题型：

BST Solved By Recursion/DFS
non-BST Solved By Recursion/DFS
Solved By Queue/BFS
Solved By Iteration
Morris Traversal

Problems

1. BST Solved By Recursion/DFS

利用到了BST的性质，每次找在左子树或右子树查找，O(lgn) 详见dfs 95. Unique Binary Search Trees II左右子树分别由dfs建立，for l in leftSubTrees: for r in rightSubTrees: n = TreeNode(val, left = l, right = r)
938. Range Sum of BST基础
235. Lowest Common Ancestor of a Binary Search Tree比较p,q,root.val来判断去哪颗子树dfs还是返回root\

270. Closest Binary Search Tree Value都不需要递归，while loop即可
285. Inorder Successor in BST

也可以用iterator找，但没有利用到bst的性质, O(n)。 recursion利用到了次性质，O（lgn), 分为三种情况：

root = p: 返回右子树最左值
root < p: 在右子树找，要是找不到，就返回none, 上一层recursion 会处理
root > p : 现在左子树找，要是找到，就是了；要是找不到，也不可能在上一层，就返回 root 776. Split BST 776. Split BST比较root.val和target,自递归左右子树，O(lgn）,空间O(lgn)；可以通过设smallerHead， greaterHead的方法，不用递归将空间将为O(1)

2. non-BST Solved By Recursion/DFS

化为 divide & Conquer，左右子树都要查找， O(n) 104. Maximum Depth of Binary Tree基本
101. Symmetric TreeRecursion over sym(left->left, right->right) && sym(left->right, right->left)
108. Convert Sorted Array to Binary Search TreeRecursion by picking up the median element each time. 似乎没用到bst的性质\

129. Sum Root to Leaf Numbers
222. Count Complete Tree Nodes
236. Lowest Common Ancestor of a Binary Tree
314. Binary Tree Vertical Order Traversal因为最后需要按照从高到低，从左到右输出，故存于res[pos][h]，依照h排序后输出;用bfs因为不用记录row, 且自然是由左向右，更容易，结果存于memo[col]=list中，设minCol, maxCol可优化为O（n)
987. Vertical Order Traversal of a Binary Tree和314的唯一区别在于对于同样高度和列的值需要按照value排序
450. Delete Node in a BST

分三种情况：
1） 叶节点 -> 直接删除
2） 有右子树 -> 找到右子树最左节点，以其值newVal替换根结点，delete(node.right, newVal）
3） 只有左子树 -> 找到左子树最右节点，以其值newVal替换根结点，delete(node.left, newVal）

105. Construct Binary Tree from Preorder and Inorder Traversal由preorder第一个元素为root， idx = inorder.index(root), 将inorder 分为左右两部分
106. Construct Binary Tree from Inorder and Postorder Traversal同上\

112. Path Sum基础
113. Path Sum II基础
437. Path Sum III记录memo[cumsum]=从根开始的路径的个数， dfs\

124. Binary Tree Maximum Path Sum返回包含node的最大path值，同时更新res = max(res, max(0, leftGain)+max(0, rightGain)+node.val)\

156. Binary Tree Upside Down不是很看得懂题目
236. Lowest Common Ancestor of a Binary Treerecursion, 若左右都有返回值，则返回母节点，否则左/右/空
250. Count Univalue Subtrees方法类似lca
261. Graph Valid Tree从0开始dfs，若有已经visited的点，说明存在环。最后判断是否所有点已被访问
297. Serialize and Deserialize Binary Tree用bfs/dfs均可；dfs， pre-order traversal, 时传递data 指数idx，(或作为全局变量,或每次pop出data处理过的值，传参data)
536. Construct Binary Tree from String类似于297，传递idx，并返回
333. Largest BST Subtreedfs, 返回bstSize, minBST, maxBST
366. Find Leaves of Binary Tree用求height一样的方法解，因为添加到res的顺序都是从最底层开始，所以res可以为数组，res[i]代表第高度i + 1层，无需排序
543. Diameter of Binary Treedfs, res = max(res, leftDepth + rightDepth)
545. Boundary of Binary Tree 545. Boundary of Binary Treedfs()中遍历所有点，若为叶节点加入，若有左子树,左边界为[root.val]+dfs(左子树）返回的左边界，有边界可以共享dfs
606. Construct String from Binary Tree 652. Find Duplicate SubtreesSerialize the tree when traversing, compare the node serialization with the hashed value.
872. Leaf-Similar Treesdfs分别得到两树的leaf list，比较\
979. Distribute Coins in Binary Tree从根结点无法判断应该如何分配，可以从叶节点自下而上分配 -> dfs, 每个节点的excess = current.val + 从左子树来的多余的coin + 从右子树来的多余的coin - 1
1110. Delete Nodes And Return Forest自下而上：先dfs左右子树，再决定node是否删除；若是其更新的左右子树添加至res；若dfs在添加之后再做，则难以解决其子树仍需要删除的情况
1372. Longest ZigZag Path in a Binary Treedfs(node, left/right flag, 以及目前zigzag 长度
298. Binary Tree Longest Consecutive Sequence类似于298，传参包含该点的最长连续路径
2458. Height of Binary Tree After Subtree Removal Queries

1)先用dfs产生每点的depth和height. 2)总结depthMap = {depth:[node.val依照height逆序排列} 3)对于query点，找到其depth, 对处于height[depth]的第一个，则代表为height最高的点，则返回第二高的height + depth; 否则不影响原来最大身高。 depth 为自根结点开始向下数，height 则为从叶节点开始向上数。

1448. Count Good Nodes in Binary Tree 1457. Pseudo-Palindromic Paths in a Binary Tree由path^(1<<node.val)来调整奇偶；由path&(path-1)==0来判断是不是只有一个奇数；A&(A-1)常被用来消除最后一个1\

3. Solved By Queue/BFS

116. Populating Next Right Pointers in Each Node and 117. Populating Next Right Pointers in Each Node II都可以由queue结局，但可以更简化。
116. Populating Next Right Pointers in Each Node

逐层遍历，链接curr所在层的下一层，curr.left.next = curr.right, curr.right.next = curr.next.left, 因为是perfect tree, 所以每一层的head必为上一层head.left.

117. Populating Next Right Pointers in Each Node II

因为不再是perfect tree，所以需要在每层第一个节点出现时设head,以及设置prev变量，每次出现node.left或node.right时，与prev相连. 199. Binary Tree Right Side Viewbfs/dfs均可
863. All Nodes Distance K in Binary Tree先将tree化为graph，再从target出发，bfs找到第k层
742. Closest Leaf in a Binary Tree同863，先将tree化为graph，再从target出发，bfs找到最先的叶节点\

102. Binary Tree Level Order TraversalUse a queue to keep track of the nodes each level.若按height order(由下自上），则需要用dfs
103. Binary Tree Zigzag Level Order Traversal类似102, 设置levelCnt, 奇数时顺序加，偶数时逆序加
337. House Robber IIIdfs返回include,notInclude, 其中notInclude=左边最大值（可以include,也可以不include) + 右边
662. Maximum Width of Binary Tree bfs, 怎么判断宽度？queue中存（node, idx), left child of A[i] = A[i] * 2, right child of A[i] = A[i] * 2 + 1, 这样宽度即为q[-1].index-q[0].index+1
1161. Maximum Level Sum of a Binary Tree 2641. Cousins in Binary Tree IIq中pop出node时，计算下一层所有node的总和，以及该node的孩子和sibiling_sum,提前令node.left.val = -1 * sibiling_sum,压入queue中\

4. Solved By Iteration

Since the concept of recursion winding/unwinding is based on a stack, there is a thumb rule that every recursive solution can be converted to an iterative approach by using a stack.

99. Recover Binary Search Treedfs/iteration, 记录变了pred, x, y, inordertraverse，当第一次node.val < pred.val时，设x=pred,y=node, 第二次出现时y=node，break；由morris traversal只用O（1）空间
530. Minimum Absolute Difference in BSTcan be solved by DFS, but easier to be solved iteratively
230. Kth Smallest Element in a BSTcan be solved by DFS, but easier to be solved iteratively
98. Validate Binary Search Treecan be solved by DFS, but easier to be solved iteratively
173. Binary Search Tree Iterator
426. Convert Binary Search Tree to Sorted Doubly Linked List无需bst
285. Inorder Successor in BST无需用到bst的性质，O(n);但若用divide & Conquer（dfs)可以减少至O(lgn)
272. Closest Binary Search Tree Value IIinorder遍历，同时maintain window deque, 当新加入的node.val - target比deque头小时pop出头部，否则停止, O(n), O(n+deque size)；recursion也可以，但我觉得iteration更直观\

5. Morris Traversal

For any kind of tree traversal, we always have the easiest of solutions which is based on recursion. Next, we have a custom stack based iterative version of the same solution. Finally, we want a tree traversal that doesn't use any kind of additional space at all. There is a well known tree traversal out there that doesn't use any additional space at all. It's known as Morris Traversal, space O(1), time O(n).

void inorderMorrisTraversal(TreeNode *root) {
 2     TreeNode *cur = root, *prev = NULL;
 3     while (cur != NULL):
 5         if (cur->left == NULL):          // 1.
 8             cur = cur->right;
10         else:
12             // find predecessor
13             prev = cur->left
14             while (prev->right != NULL && prev->right != cur):
15                 prev = prev->right
16 
17             if (prev->right == NULL):   // 2.a)
19                 prev->right = cur;
20                 cur = cur->left;
22             else:                       // 2.b)
24                 prev->right = NULL;
26                 cur = cur->right;

114. Flatten Binary Tree to Linked List利用morris traversal,不断的将现在节点的左孩子设为现在节点的右孩子，现在节点原来的右孩子连接到原来左子树的最右。
99. Recover Binary Search Tree