前序遍历：根 - 左 - 右
preorder: root - left - right
144. Binary Tree Preorder Traversal
注意：判断root是否为空
class Solution {
//recursive
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<Integer>();
return recursive(root, list);
}
public List<Integer> recursive(TreeNode root, List<Integer> list){
if(root!=null){
list.add(root.val);
recursive(root.left, list);
recursive(root.right, list);
}
return list;
}
//stack
public List<Integer> preorderTraversal2(TreeNode root) {
Stack<TreeNode> tree = new Stack<>();
List<Integer> list = new ArrayList<Integer>();
if(root!=null) tree.push(root);
while(!tree.isEmpty()){
root = tree.pop();
list.add(root.val);
if(root.right!=null) tree.push(root.right);
if(root.left!=null) tree.push(root.left);
}
return list;
}
}
中序遍历：左 - 根 - 右
inorder traversal: left - root - right
94. Binary Tree Inorder Traversal
class Solution {
//recursive
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<Integer>();
recursive(root, list);
return list;
}
public void recursive(TreeNode root, List<Integer> list){
if(root!=null){
recursive(root.left, list);
list.add(root.val);
recursive(root.right, list);
}
}
//stack
public List<Integer> inorderTraversal2(TreeNode root) {
List<Integer> list = new ArrayList<Integer>();
Stack<TreeNode> tree = new Stack<>();
while(root!=null || !tree.isEmpty()){
while(root!=null){
tree.push(root);
root=root.left;
}
root=tree.pop();
list.add(root.val);
root=root.right;
}
return list;
}
}
173. Binary Search Tree Iterator
public class BSTIterator {
private TreeNode root;
private TreeNode cur;
private Stack<TreeNode> stack;
public BSTIterator(TreeNode root) {
this.root = root;
this.cur = root;
stack = new Stack<>();
}
/** @return whether we have a next smallest number */
public boolean hasNext() {
if(root!=null || !stack.isEmpty()) {
cur=root;
while(cur!=null) {
stack.push(cur);
cur=cur.left;
}
cur=stack.pop();
root=cur.right;
return true;
}
return false;
}
/** @return the next smallest number */
public int next() {
return cur.val;
}
}
不知道hasNext()的时间复杂度是不是average O(1)。
还需要返工。
参考：https://www.cnblogs.com/AnnieKim/archive/2013/06/15/MorrisTraversal.html
后序遍历：左 - 右 - 根 （从叶子结点开始遍历，便于求和）
postorder: left - right - root
145. Binary Tree Postorder Traversal
class Solution {
//recursive
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
recursive(root, list);
return list;
}
public void recursive(TreeNode root, List<Integer> list){
if(root != null){
recursive(root.left, list);
recursive(root.right, list);
list.add(root.val);
}
}
//stack
public List<Integer> postorderTraversal(TreeNode root) {
//注意这里是linkedlist
LinkedList<Integer> list = new LinkedList<>();
if(root==null) return list;
Stack<TreeNode> tree = new Stack<>();
tree.push(root);
while(!tree.isEmpty()){
root=tree.pop();
list.addFirst(root.val);
if(root.left!=null) tree.push(root.left);
if(root.right!=null) tree.push(root.right);
}
return list;
}
}
563. Binary Tree Tilt
543. Diameter of Binary Tree
找每一个node下最长的path：左孩子最大深度+右孩子最大深度+2
找一个node的最大深度：max(左孩子最大深度，右孩子最大深度) + 1
class Solution {
private int longest = 0;
public int diameterOfBinaryTree(TreeNode root) {
maxDepth(root);
return longest;
}
public int maxDepth(TreeNode root) {
if(root==null) return -1;
int left = maxDepth(root.left);
int right = maxDepth(root.right);
longest = Math.max(left + right + 2, longest);
return Math.max(left, right) + 1;
}
}
687. Longest Univalue Path
124. Binary Tree Maximum Path Sum
几个陷阱：
path至少包含一个结点，相当于无向图，求任意两结点之间值的最大值。
如果返回根节点，每一层都只能右一个点。
class Solution {
private int largest;
public int maxPathSum(TreeNode root) {
largest = root.val;
largestPath(root);
return largest;
}
//递归：必须经过根节点 / 只有一边的子节点被用到
public int largestPath(TreeNode node) {
if(node==null) return 0;
//有三种选择：左+右+根，左+根，右+根
//如果是负值，直接变为零
int left = Math.max(0, largestPath(node.left));
int right = Math.max(0, largestPath(node.right));
largest = Math.max(left + right + node.val, largest);
return Math.max(left, right) + node.val;
}
}
参考：https://www.youtube.com/watch?v=9ZNky1wqNUw&t=4s
root==null: depth=0;
only a root without left or right child: depth=1
105. Construct Binary Tree from Preorder and Inorder Traversal
preorder的start是当前根节点，inoder找到当前根节点之后，它左边都是左子树，右边都是右子树。让当前root的index是i。
root.left就找[instart, i-1]，root.right就找[i+1, end]
root.left的prestart就是prestart+1
root.right的prestart就是prestart+左边元素个数+1
左边元素个数是i-instart
//pre: 根 左 右
//in: 左 根 右
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
return helper (0, 0, preorder.length-1, preorder, inorder);
}
public TreeNode helper (int preStart, int inStart, int end, int[] preorder, int[] inorder) {
if(preStart>preorder.length-1 || inStart>end) return null;
TreeNode root = new TreeNode(preorder[preStart]);
int i=inStart;
while(i<= end){
if(inorder[i]==preorder[preStart]) break;
i++;
}
root.left=helper (preStart+1, inStart, i-1, preorder, inorder);
root.right=helper (preStart+i-inStart+1, i+1, end, preorder, inorder);
return root;
}
}
106. Construct Binary Tree from Inorder and Postorder Traversal
同上一题
class Solution {
public TreeNode buildTree(int[] inorder, int[] postorder) {
return helper(0, postorder.length-1, inorder.length-1, inorder, postorder);
}
public TreeNode helper(int in_str, int post_str, int in_end, int[] inorder, int[] postorder) {
if(post_str<0 || in_end<in_str) return null;
TreeNode root = new TreeNode(postorder[post_str]);
int i = 0; // the posit of root
while(inorder[i]!=postorder[post_str]) i++;
root.right = helper(i+1, post_str-1, in_end, inorder, postorder);
root.left = helper(in_str, post_str-in_end+i-1, i-1, inorder, postorder);
return root;
}
}
完全二叉树 Complete Binary Tree
只有最后一层可以不被填满，不被填满的空缺全都集中在右边
特点：如果全都被填满，node个数是2^h-1。
222. Count Complete Tree Nodes
思路： 求左子树深度和右子树深度之差，如果深度相同，说明node全满，直接用公式求node个数。
沿着左子树的左边求左子树深度，沿着右子树的左边求右子树深度，如果两边深度相同，说明左子树是满的，如果两边不同，说明右子树是满的。
位运算比pow()快很多
//time: O(logn*logn) space: O(n)
class Solution {
public int countNodes(TreeNode root) {
if(root==null) return 0;
int left = depth(root.left);
int right = depth(root.right);
if(left==right) return (1 << left) + countNodes(root.right);
else return (1 << right) + countNodes(root.left);
}
public int depth(TreeNode root) {
int depth=0;
while(root!=null){
root=root.left;
depth++;
}
return depth;
}
}
网友评论