LeetCode：二叉树_综合

二叉树锯齿形遍历

103：给定一个二叉树，返回其节点值的锯齿形层序遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

class Solution {public List<List<Integer>> zigzagLevelOrder(TreeNode root) {int depth = 0;Deque<TreeNode> queue = new LinkedList<>();List<List<Integer>> result = new LinkedList<>();if(root==null)return result;queue.offer(root);//本质和层次遍历的顺序一样，只是存放结果的时候，是正序还是逆序while(!queue.isEmpty()){depth++;int size = queue.size();List<Integer> level = new LinkedList<>();for(int i=0;i<size;i++){   TreeNode cur = queue.poll();           level.add(cur.val);  if(cur.left!=null)queue.offer(cur.left);if(cur.right!=null)queue.offer(cur.right);                }if(depth%2==0)Collections.reverse(level);result.add(level);}return result;}
}

二叉搜索树最近公共祖先

剑指offer 68：给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if(root.val>p.val && root.val>q.val){return lowestCommonAncestor(root.left,p,q);}if(root.val<p.val&&root.val<q.val){return lowestCommonAncestor(root.right,p,q);}return root;}
}

二叉树的右视图

199：给定一个二叉树的根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

class Solution {public List<Integer> rightSideView(TreeNode root) {List<Integer> res = new ArrayList<>();Queue<TreeNode> queue = new LinkedList<>();if(root!=null) queue.offer(root);while(!queue.isEmpty()){int size = queue.size();//下一层的元素个数for(int i = 0 ;i<size;i++){TreeNode cur = queue.poll();if(i==size-1)//这一层的最后一个元素res.add(cur.val);if(cur.left!=null)queue.offer(cur.left);if(cur.right!=null)queue.offer(cur.right);}}return res;}
}

求根节点到叶节点数字之和

129：计算从根节点到叶节点生成的 所有数字之和 。

class Solution {public int sumNumbers(TreeNode root) {     if(root ==null)return 0;return countHelper(root,0);}public int countHelper(TreeNode root,int result){result = result*10+root.val;//如果当前是叶子节点返回结果if(root.left == null&&root.right==null)return result;int left=0,right=0;if(root.left!=null)left = countHelper(root.left,result);if(root.right!=null)right = countHelper(root.right,result);return left+right;}}

二叉树中的最大路径和

124：路径被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中至多出现一次。该路径至少包含一个节点，且不一定经过根节点。

路径和是路径中各节点值的总和。给你一个二叉树的根节点 root ，返回其最大路径和。

class Solution {int max = Integer.MIN_VALUE;public int maxPathSum(TreeNode root) {inOrder(root);return max;}public int inOrder(TreeNode root){if(root == null)return 0;//如果左边来的路径小于0，不如取0int left = Math.max(0,inOrder(root.left));//如果右边来的路径小于0，不如取0int right =Math.max(0,inOrder(root.right));//当前节点作为转折点的最大值与最大值对比max = Math.max(max,left+right+root.val);//返回给父节点较大的一条路径return Math.max(left,right)+root.val;}}

二叉树的路径总和

112：给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。

class Solution {public boolean hasPathSum(TreeNode root, int targetSum) {if(root ==null)return false;return travel(root,targetSum-root.val);}public boolean travel(TreeNode root,int targetSum){if(root.left==null&&root.right==null&&targetSum==0)return true;boolean left=false, right=false;if(root.left!=null){left = travel(root.left,targetSum-root.left.val);}if(left)//左边有结果直接返回return true;if(root.right!=null){right = travel(root.right,targetSum-root.right.val);}return right;}}

public class Solution {public boolean hasPathSum (TreeNode root, int sum) {// write code herereturn travel(root,0,sum);}public boolean travel(TreeNode root,int curSum,int sum){if(root == null){return false;}curSum += root.val;if(root.left == null && root.right == null && curSum == sum){return true;}return travel(root.left,curSum,sum) || travel(root.right,curSum,sum);  }
}

二叉树的路径总和II

113：给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有从根节点到叶子节点路径总和等于给定目标和的路径。叶子节点是指没有子节点的节点。

class Solution {List<List<Integer>> res = new LinkedList<>();Deque<Integer> path = new LinkedList<>();public List<List<Integer>> pathSum(TreeNode root, int targetSum) {if(root==null) return  res;path.offer(root.val);traverl(root,targetSum-root.val);return res;}public void traverl(TreeNode root,int targetSum){if(root==null) return;//找到正确的路径if(targetSum==0&&root.left==null&&root.right==null)res.add(new LinkedList<Integer>(path));//遍历左子树   if(root.left!=null){          //左孩子节点加入pathpath.offer(root.left.val);traverl(root.left,targetSum-root.left.val);//左孩子节点弹出pathpath.pollLast();}//遍历右子树if(root.right!=null){//右孩子节点加入pathpath.offer(root.right.val);traverl(root.right,targetSum-root.right.val);//右孩子节点加入pathpath.pollLast();}}
}

前序遍历和中序遍历构建二叉树

class Solution {public TreeNode buildTree(int[] preorder, int[] inorder) {int length = preorder.length;return build(preorder,inorder,0,length-1,0,length-1);}public TreeNode build(int[] preorder,int[] inorder,int preStart,int preEnd,int inStart,int inEnd){if(preStart>preEnd||inStart>inEnd)return null;if(preStart==preEnd)return new TreeNode(preorder[preStart]);TreeNode root = new TreeNode(preorder[preStart]);int mid =0;for(int i=inStart;i<=inEnd;i++){if(inorder[i]==preorder[preStart]){mid = i;break;}}int leftlength = mid-inStart;root.left=build(preorder,inorder,preStart+1,preStart+leftlength,inStart,mid-1);root.right=build(preorder,inorder,preStart+leftlength+1,preEnd,mid+1,inEnd);return root;}
}

对称二叉树

101：给定一个二叉树，检查它是否是镜像对称的。

class Solution {public boolean isSymmetric(TreeNode root) {return symmetric(root.left,root.right);}public boolean symmetric(TreeNode left,TreeNode right){if(left==null&&right!=null)return false;if(left!=null&&right==null)return false;if(left==null&&right==null)return true;if(left.val!=right.val) return false;boolean outside = symmetric(left.left,right.right);boolean inside = symmetric(left.right,right.left);return outside&&inside;}
}

验证二叉搜索树

98：给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

递归：中序遍历

class Solution {long pre = Long.MIN_VALUE;public boolean isValidBST(TreeNode root) {if(root==null)return true;if(!isValidBST(root.left))return false;if(root.val<=pre)return false;pre = root.val;return isValidBST(root.right);}
}

迭代：中序遍历

class Solution {public boolean isValidBST(TreeNode root) {Deque<TreeNode> stack = new LinkedList<>();TreeNode pre = null;stack.push(root);while(!stack.isEmpty()){TreeNode cur = stack.pop();if(cur!=null){if(cur.right!=null)stack.push(cur.right);stack.push(cur);stack.push(null);if(cur.left!=null)stack.push(cur.left);}else{cur = stack.pop();if(pre!=null&&cur.val<=pre.val)return false;pre = cur;}}return true;}
}

验证完全二叉树

958：给定一个二叉树，确定它是否是一个完全二叉树。

class Solution {public boolean isCompleteTree(TreeNode root) {LinkedList<TreeNode> queue = new LinkedList<>();queue.offer(root);while(!queue.isEmpty()){TreeNode cur = queue.poll();//如果当前节点为空，队列后面应该都为空if(cur==null){while(!queue.isEmpty()){if(queue.poll()!=null)return false;}}else{queue.offer(cur.left);queue.offer(cur.right);}}return true;}
}

二叉树的直径

543：给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。

class Solution {int max = 0;public int diameterOfBinaryTree(TreeNode root) {int depth = getDepth(root);return max;}public int getDepth(TreeNode root){if(root==null)return 0;int leftdepth = getDepth(root.left);int rightdepth = getDepth(root.right);int pathlength = leftdepth+rightdepth;max = Math.max(max,pathlength);return Math.max(leftdepth,rightdepth)+1;}
}

二叉树的最大深度

求根节点高度

class Solution {public int maxDepth(TreeNode root) {if(root==null) return 0;return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;}
}

层次遍历：

class Solution {public int maxDepth(TreeNode root) {if(root==null)return 0;Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);int depth = 0;while (!queue.isEmpty()) {//记录每层有多少个int size = queue.size();//每层遍历完之后 深度加1while (size > 0) {TreeNode node = queue.poll();if(node.left!=null)queue.offer(node.left);if(node.right!=null)queue.offer(node.right);size--;}depth++;}return depth;}

十四、二叉树的最小深度

递归：后序遍历

class Solution {public int minDepth(TreeNode root) {if(root==null) return 0;if(root.left==null&&root.right!=null)return minDepth(root.right)+1;if(root.right==null&&root.left!=null)return minDepth(root.left)+1;return Math.min(minDepth(root.left),minDepth(root.right))+1;}
}

层次遍历，遇到叶子就返回

class Solution {public int minDepth(TreeNode root) {Deque<TreeNode> queue = new LinkedList<>();if(root!=null) queue.offer(root);int depth=0;while(!queue.isEmpty()){depth++;int size = queue.size();for(int i =0;i<size;i++){TreeNode cur = queue.poll();if(cur.left!=null)queue.offer(cur.left);if(cur.right!=null)queue.offer(cur.right);if(cur.left==null&&cur.right==null)return depth;}}return depth;}
}

二叉树最大宽度

662：给定一个二叉树，编写一个函数来获取这个树的最大宽度。树的宽度是所有层中的最大宽度。

class Solution {public int widthOfBinaryTree(TreeNode root) {LinkedList<PositionNode> queue = new LinkedList<>();queue.offer(new PositionNode(root,1));int max=0;while(!queue.isEmpty()){int size = queue.size();int left=Integer.MAX_VALUE;int right = Integer.MIN_VALUE;for(int i=0;i<size;i++){PositionNode cur = queue.poll();if(i==0)left = cur.index;if(i==size-1)right = cur.index;if(cur.root.left!=null)queue.offer(new PositionNode(cur.root.left,cur.index*2));if(cur.root.right!=null)queue.offer(new PositionNode(cur.root.right,cur.index*2+1));}max = Math.max(max,right-left+1);} return max;}
}class PositionNode{TreeNode root;int index;PositionNode(){};PositionNode(TreeNode root,int index){this.root = root;this.index = index;}
}

平衡二叉树

110：给定一个二叉树，判断它是否是高度平衡的二叉树。

class Solution {public boolean isBalanced(TreeNode root) {return getHeight(root)!=-1;}public int getHeight(TreeNode root){if(root==null) return 0;int leftHeight = getHeight(root.left);int rightHeight = getHeight(root.right);if(leftHeight==-1||rightHeight==-1)return -1;return Math.abs(leftHeight-rightHeight)>1?-1:Math.max(leftHeight,rightHeight)+1;}
}

翻转二叉树

前序遍历递归翻转：

class Solution {public TreeNode invertTree(TreeNode root) {if(root==null) return root;//前序遍历，根节点直接反转左右子树TreeNode left = root.left;TreeNode right = root.right;root.left = right;root.right = left;  //左右子树再进行反转invertTree(root.left);invertTree(root.right);return root;}
}

层次遍历翻转：

class Solution {public TreeNode invertTree(TreeNode root) {Deque<TreeNode> queue = new LinkedList<>();if(root != null) queue.offer(root);while(!queue.isEmpty()){int size = queue.size();for(int i =0;i<size;i++){//反转当前节点TreeNode cur = queue.poll();TreeNode left = cur.left;TreeNode right = cur.right;cur.right = left;cur.left = right;//左右子树放入队列等待遍历if(cur.right!=null)queue.offer(cur.right);if(cur.left!=null)queue.offer(cur.left);}}return root;}
}

二叉搜索树第K小元素

中序递归遍历

class Solution {int k;int res;public int kthSmallest(TreeNode root, int k) {this.k=k;inorder(root);return res;}public void inorder(TreeNode root){//如果为空返回if(root==null)return ;inorder(root.left);//k减1，判断是否是第k个k--;if(k==0)res = root.val;inorder(root.right);}
}

二叉树展开为链表

114：给你二叉树的根结点 root ，请你将它展开为一个单链表：展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。展开后的单链表应该与二叉树 先序遍历 顺序相同。

递归：后序遍历

class Solution {TreeNode pre = null;public void flatten(TreeNode root) {if(root==null)return ;flatten(root.right);flatten(root.left);root.left = null;root.right = pre;pre = root;}
}

迭代：前序遍历

class Solution {public void flatten(TreeNode root) {if(root==null)return ;Deque<TreeNode> stack = new LinkedList<>();TreeNode pre = null;stack.push(root);while(!stack.isEmpty()){TreeNode cur = stack.pop();TreeNode left = cur.left;TreeNode right = cur.right;if(pre==null){pre = cur;pre.left = null;}else{pre.right = cur;pre.left = null;pre = pre.right;}if(right!=null)stack.push(right);if(left!=null)stack.push(left);         }return ;}
}

二叉树展开为双向链表

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。

class Solution {public Node treeToDoublyList(Node root) {LinkedList<Node> stack = new LinkedList<>();if(root==null){return null;}     Node head = null;Node pre = null;stack.push(root);while(!stack.isEmpty()){Node cur = stack.pop();if(cur!=null){if(cur.right!=null)stack.push(cur.right);stack.push(cur);stack.push(null);if(cur.left!=null)stack.push(cur.left);}else{  cur = stack.pop();if(pre ==null){pre = cur;head = cur;}else{pre.right = cur;cur.left = pre;pre = pre.right;}}}pre.right = head;head.left = pre;return head;}
}

树的遍历

1、递归前序遍历

class Solution {public List<Integer> preorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();traversal(root,result);return result;}public void traversal(TreeNode root,List<Integer> result){if(root==null){return ;}result.add(root.val);traversal(root.left,result);traversal(root.right,result);}
}

2、非递归前序遍历

class Solution {public List<Integer> preorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();Stack<TreeNode> stack = new Stack<>();if(root!=null){stack.push(root);}while(!stack.isEmpty()){TreeNode node = stack.pop();if(node!=null){if(node.right!=null){stack.push(node.right);}if(node.left!=null){stack.push(node.left);}stack.push(node);stack.push(null);}else{TreeNode cur = stack.pop();result.add(cur.val);}}return result;}
}

3、递归中序遍历

class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();traversal(root,result);return result;}public void traversal(TreeNode root,List<Integer> result){if(root==null){return ;}traversal(root.left,result);result.add(root.val);traversal(root.right,result);}
}

4、非递归中序遍历

class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();Stack<TreeNode> stack = new Stack<>();if(root!=null){stack.push(root);}while(!stack.isEmpty()){TreeNode node = stack.pop();if(node!=null){if(node.right!=null){stack.push(node.right);}stack.push(node);stack.push(null);if(node.left!=null){stack.push(node.left);}}else{TreeNode cur = stack.pop();result.add(cur.val);}}return result;}}

5、递归后序遍历

class Solution {public List<Integer> postorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();traversal(root,result);return result;}public void traversal(TreeNode root,List<Integer> result){if(root==null){return ;}traversal(root.left,result);traversal(root.right,result);result.add(root.val);}
}

6、非递归后序遍历

class Solution {public List<Integer> postorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();Stack<TreeNode> stack = new Stack<>();if(root!=null){stack.push(root);}while(!stack.isEmpty()){TreeNode node = stack.pop();if(node!=null){stack.push(node);stack.push(null);if(node.right!=null){stack.push(node.right);}if(node.left!=null){stack.push(node.left);}}else{TreeNode cur = stack.pop();result.add(cur.val);}}return result;}
}

7、层次遍历

class Solution {public List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> result = new ArrayList<>();Queue<TreeNode> queue = new LinkedList<>();if(root!=null){queue.offer(root);}while(!queue.isEmpty()){List<Integer> levelResult = new ArrayList<>();int size = queue.size();for(int i =0;i<size;i++){TreeNode node = queue.poll();levelResult.add(node.val);if(node.left!=null){queue.offer(node.left);}if(node.right!=null){queue.offer(node.right);}}result.add(levelResult);}return result;}
}

另一棵树的子树

572：给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。

class Solution {public boolean isSubtree(TreeNode root, TreeNode subRoot) {if(subRoot==null){return true;}if(root==null){return false;}return isEqual(root,subRoot) || isSubtree(root.left,subRoot) || isSubtree(root.right,subRoot);}public boolean isEqual(TreeNode root1, TreeNode root2){if(root1 == null && root2 ==null){return true;}if(root1 == null || root2 ==null){return false;}if(root1.val!=root2.val){return false;}return isEqual(root1.left,root2.left)&&isEqual(root1.right,root2.right);}
}

树的子结构

剑指offer26：输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)。B是A的子结构，即 A中有出现和B相同的结构和节点值。

class Solution {public boolean isSubStructure(TreeNode A, TreeNode B) {return (A!=null&&B!=null)&& (isContain(A,B) || isSubStructure(A.left,B) || isSubStructure(A.right,B));}public boolean isContain(TreeNode A, TreeNode B){if( B==null ){return true;}if(A==null||A.val!=B.val){return false;}return isContain(A.left,B.left)&&isContain(A.right,B.right);}
}