devbox
Monodyee
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

LeetCode：二叉树_public int[] inorder(treenode root)

作者：Monodyee | 2024-06-01 04:52:47

赞

踩

public int[] inorder(treenode root)

二叉树锯齿形遍历

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

  1. class Solution {
  2.     public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
  3.         int depth = 0;
  4.         Deque<TreeNode> queue = new LinkedList<>();
  5.         List<List<Integer>> result = new LinkedList<>();
  6.         if(root==null)
  7.             return result;
  8.         queue.offer(root);
  9.         //本质和层次遍历的顺序一样，只是存放结果的时候，是正序还是逆序
  10.         while(!queue.isEmpty()){
  11.             depth++;
  12.             int size = queue.size();
  13.             List<Integer> level = new LinkedList<>();
  14.             for(int i=0;i<size;i++){   
  15.                 TreeNode cur = queue.poll();           
  16.                 level.add(cur.val);  
  17.                 if(cur.left!=null)
  18.                     queue.offer(cur.left);
  19.                 if(cur.right!=null)
  20.                     queue.offer(cur.right);                
  21.             }
  22.             if(depth%2==0)
  23.                 Collections.reverse(level);
  24.             result.add(level);
  25.         }
  26.         return result;
  27.     }
  28. }

最近公共祖先

236：最近公共祖先的定义为：对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。

  1. class Solution {
  2.     public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
  3.         //如果本节点为p或者q，将自己返回出去
  4.         if(root==p||root==q||root==null)
  5.             return root;
  6.         //后序遍历，看看左右子树是否含有p q
  7.         TreeNode left = lowestCommonAncestor(root.left,p,q);
  8.         TreeNode right = lowestCommonAncestor(root.right,p,q);
  9.         //左右子树分别含有p和q
  10.         if(left!=null&&right!=null)
  11.             return root;
  12.         //左子树含有p或者q，右子树没有
  13.         else if(left!=null&&right==null)
  14.             return left;
  15.         //右子树含有p或者q，左子树没有
  16.         else if(left==null&&right!=null)
  17.             return right;
  18.         else
  19.             return null;
  20.     }
  21. }

二叉搜索树最近公共祖先

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

  1. class Solution {
  2.     public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
  3.         if(root.val>p.val && root.val>q.val){
  4.             return lowestCommonAncestor(root.left,p,q);
  5.         }
  6.         if(root.val<p.val&&root.val<q.val){
  7.             return lowestCommonAncestor(root.right,p,q);
  8.         }
  9.         return root;
  10.     }
  11. }

二叉树的右视图

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

  1. class Solution {
  2.     public List<Integer> rightSideView(TreeNode root) {
  3.         List<Integer> res = new ArrayList<>();
  4.         Queue<TreeNode> queue = new LinkedList<>();
  5.         if(root!=null) queue.offer(root);
  6.         while(!queue.isEmpty()){
  7.             int size = queue.size();//下一层的元素个数
  8.             for(int i = 0 ;i<size;i++){
  9.                 TreeNode cur = queue.poll();
  10.                 if(i==size-1)//这一层的最后一个元素
  11.                     res.add(cur.val);
  12.                 if(cur.left!=null)
  13.                     queue.offer(cur.left);
  14.                 if(cur.right!=null)
  15.                     queue.offer(cur.right);
  16.             }
  17.             
  18.         }
  19.         return res;
  20.     }
  21. }

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

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

  1. class Solution {
  2.     public int sumNumbers(TreeNode root) {     
  3.         if(root ==null)
  4.             return 0;
  5.         return countHelper(root,0);
  6.     }
  7.  
  8.     public int countHelper(TreeNode root,int result){
  9.         result = result*10+root.val;
  10.         //如果当前是叶子节点返回结果
  11.         if(root.left == null&&root.right==null)
  12.             return result;
  13.         int left=0,right=0;
  14.         if(root.left!=null)
  15.             left = countHelper(root.left,result);
  16.         if(root.right!=null)
  17.             right = countHelper(root.right,result);
  18.         return left+right;
  19.     }
  20.  
  21. }

二叉树中的最大路径和

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

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

  1. class Solution {
  2.     int max = Integer.MIN_VALUE;
  3.     public int maxPathSum(TreeNode root) {
  4.         inOrder(root);
  5.         return max;
  6.     }
  7.     public int inOrder(TreeNode root){
  8.         if(root == null)
  9.             return 0;
  10.         //如果左边来的路径小于0，不如取0
  11.         int left = Math.max(0,inOrder(root.left));
  12.         //如果右边来的路径小于0，不如取0
  13.         int right =Math.max(0,inOrder(root.right));
  14.         //当前节点作为转折点的最大值与最大值对比
  15.         max = Math.max(max,left+right+root.val);
  16.         //返回给父节点较大的一条路径
  17.         return Math.max(left,right)+root.val;
  18.     }
  19.  
  20. }

二叉树的路径总和 

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

  1. class Solution {
  2.     public boolean hasPathSum(TreeNode root, int targetSum) {
  3.         if(root ==null)
  4.             return false;
  5.         return travel(root,targetSum-root.val);
  6.     }
  7.  
  8.     public boolean travel(TreeNode root,int targetSum){
  9.         if(root.left==null&&root.right==null&&targetSum==0)
  10.             return true;
  11.         boolean left=false, right=false;
  12.         if(root.left!=null){
  13.             left = travel(root.left,targetSum-root.left.val);
  14.         }
  15.         if(left)//左边有结果直接返回
  16.             return true;
  17.         if(root.right!=null){
  18.             right = travel(root.right,targetSum-root.right.val);
  19.         }
  20.         return right;
  21.     }
  22.  
  23. }
  1. public class Solution {
  2.     public boolean hasPathSum (TreeNode root, int sum) {
  3.         // write code here
  4.         return travel(root,0,sum);
  5.     }
  6.     
  7.     public boolean travel(TreeNode root,int curSum,int sum){
  8.         if(root == null){
  9.             return false;
  10.         }
  11.         curSum += root.val;
  12.         if(root.left == null && root.right == null && curSum == sum){
  13.             return true;
  14.         }
  15.         return travel(root.left,curSum,sum) || travel(root.right,curSum,sum);  
  16.     }
  17. }

二叉树的路径总和II

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

  1. class Solution {
  2.     List<List<Integer>> res = new LinkedList<>();
  3.     Deque<Integer> path = new LinkedList<>();
  4.  
  5.     public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
  6.         if(root==null) return  res;
  7.         path.offer(root.val);
  8.         traverl(root,targetSum-root.val);
  9.         return res;
  10.     }
  11.  
  12.     public void traverl(TreeNode root,int targetSum){
  13.         if(root==null) return;
  14.         //找到正确的路径
  15.         if(targetSum==0&&root.left==null&&root.right==null)
  16.             res.add(new LinkedList<Integer>(path));
  17.         
  18.         //遍历左子树   
  19.         if(root.left!=null){          
  20.             //左孩子节点加入path
  21.             path.offer(root.left.val);
  22.             traverl(root.left,targetSum-root.left.val);
  23.             //左孩子节点弹出path
  24.             path.pollLast();
  25.         }
  26.         //遍历右子树
  27.         if(root.right!=null){
  28.             //右孩子节点加入path
  29.             path.offer(root.right.val);
  30.             traverl(root.right,targetSum-root.right.val);
  31.             //右孩子节点加入path
  32.             path.pollLast();
  33.         }
  34.     }
  35. }

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

  1. class Solution {
  2.     public TreeNode buildTree(int[] preorder, int[] inorder) {
  3.         int length = preorder.length;
  4.         return build(preorder,inorder,0,length-1,0,length-1);
  5.     }
  6.     public TreeNode build(int[] preorder,int[] inorder,int preStart,int preEnd,int inStart,int inEnd){
  7.         if(preStart>preEnd||inStart>inEnd)
  8.             return null;
  9.         if(preStart==preEnd)
  10.             return new TreeNode(preorder[preStart]);
  11.         TreeNode root = new TreeNode(preorder[preStart]);
  12.         int mid =0;
  13.         for(int i=inStart;i<=inEnd;i++){
  14.             if(inorder[i]==preorder[preStart]){
  15.                 mid = i;
  16.                 break;
  17.             }
  18.         }
  19.         int leftlength = mid-inStart;
  20.         root.left=build(preorder,inorder,preStart+1,preStart+leftlength,inStart,mid-1);
  21.         root.right=build(preorder,inorder,preStart+leftlength+1,preEnd,mid+1,inEnd);
  22.         return root;
  23.     }
  24. }

对称二叉树

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

  1. class Solution {
  2.     public boolean isSymmetric(TreeNode root) {
  3.         return symmetric(root.left,root.right);
  4.     }
  5.  
  6.     public boolean symmetric(TreeNode left,TreeNode right){
  7.         if(left==null&&right!=null)return false;
  8.         if(left!=null&&right==null)return false;
  9.         if(left==null&&right==null)return true;
  10.         if(left.val!=right.val) return false;
  11.  
  12.         boolean outside = symmetric(left.left,right.right);
  13.         boolean inside = symmetric(left.right,right.left);
  14.         return outside&&inside;
  15.  
  16.     }
  17. }

验证二叉搜索树

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

递归：中序遍历

  1. class Solution {
  2.     long pre = Long.MIN_VALUE;
  3.     public boolean isValidBST(TreeNode root) {
  4.         if(root==null)
  5.             return true;
  6.         if(!isValidBST(root.left))
  7.             return false;
  8.         if(root.val<=pre)
  9.             return false;
  10.         pre = root.val;
  11.         return isValidBST(root.right);
  12.     }
  13. }

迭代：中序遍历

  1. class Solution {
  2.     public boolean isValidBST(TreeNode root) {
  3.         Deque<TreeNode> stack = new LinkedList<>();
  4.         TreeNode pre = null;
  5.         stack.push(root);
  6.         while(!stack.isEmpty()){
  7.             TreeNode cur = stack.pop();
  8.             if(cur!=null){
  9.                 if(cur.right!=null)
  10.                     stack.push(cur.right);
  11.                 stack.push(cur);
  12.                 stack.push(null);
  13.                 if(cur.left!=null)
  14.                     stack.push(cur.left);
  15.             }else{
  16.                 cur = stack.pop();
  17.                 if(pre!=null&&cur.val<=pre.val)
  18.                     return false;
  19.                 pre = cur;
  20.             }
  21.         }
  22.         return true;
  23.     }
  24. }

验证完全二叉树

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

  1. class Solution {
  2.     public boolean isCompleteTree(TreeNode root) {
  3.         LinkedList<TreeNode> queue = new LinkedList<>();
  4.         queue.offer(root);
  5.         while(!queue.isEmpty()){
  6.             TreeNode cur = queue.poll();
  7.             //如果当前节点为空，队列后面应该都为空
  8.             if(cur==null){
  9.                 while(!queue.isEmpty()){
  10.                     if(queue.poll()!=null)
  11.                         return false;
  12.                 }
  13.             }else{
  14.                 queue.offer(cur.left);
  15.                 queue.offer(cur.right);
  16.             }
  17.             
  18.         }
  19.         return true;
  20.     }
  21. }

二叉树的直径

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

  1. class Solution {
  2.     int max = 0;
  3.     public int diameterOfBinaryTree(TreeNode root) {
  4.         int depth = getDepth(root);
  5.         return max;
  6.     }
  7.     public int getDepth(TreeNode root){
  8.         if(root==null)
  9.             return 0;
  10.         int leftdepth = getDepth(root.left);
  11.         int rightdepth = getDepth(root.right);
  12.         int pathlength = leftdepth+rightdepth;
  13.         max = Math.max(max,pathlength);
  14.         return Math.max(leftdepth,rightdepth)+1;
  15.     }
  16. }

二叉树的最大深度

求根节点高度

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

层次遍历：

  1. class Solution {
  2.     public int maxDepth(TreeNode root) {
  3.         if(root==null)
  4.             return 0;
  5.         Queue<TreeNode> queue = new LinkedList<>();
  6.         queue.offer(root);
  7.         int depth = 0;
  8.         while (!queue.isEmpty()) {
  9.             //记录每层有多少个
  10.             int size = queue.size();
  11.             //每层遍历完之后 深度加1
  12.             while (size > 0) {
  13.                 TreeNode node = queue.poll();
  14.                 if(node.left!=null)
  15.                     queue.offer(node.left);
  16.                 if(node.right!=null)
  17.                     queue.offer(node.right);
  18.                 size--;
  19.             }
  20.             depth++;
  21.         }
  22.         return depth;
  23.  
  24.     }

十四、二叉树的最小深度

递归：后序遍历

  1. class Solution {
  2.     public int minDepth(TreeNode root) {
  3.         if(root==null) return 0;
  4.         if(root.left==null&&root.right!=null)
  5.             return minDepth(root.right)+1;
  6.         if(root.right==null&&root.left!=null)
  7.             return minDepth(root.left)+1;
  8.         return Math.min(minDepth(root.left),minDepth(root.right))+1;
  9.     }
  10. }

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

  1. class Solution {
  2.     public int minDepth(TreeNode root) {
  3.         Deque<TreeNode> queue = new LinkedList<>();
  4.         if(root!=null) queue.offer(root);
  5.         int depth=0;
  6.         while(!queue.isEmpty()){
  7.             depth++;
  8.             int size = queue.size();
  9.             for(int i =0;i<size;i++){
  10.                 TreeNode cur = queue.poll();
  11.                 if(cur.left!=null)
  12.                     queue.offer(cur.left);
  13.                 if(cur.right!=null)
  14.                     queue.offer(cur.right);
  15.                 if(cur.left==null&&cur.right==null)
  16.                     return depth;
  17.             }
  18.         }
  19.         return depth;
  20.     }
  21. }

二叉树最大宽度

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

  1. class Solution {
  2.     public int widthOfBinaryTree(TreeNode root) {
  3.         LinkedList<PositionNode> queue = new LinkedList<>();
  4.         queue.offer(new PositionNode(root,1));
  5.         int max=0;
  6.         while(!queue.isEmpty()){
  7.             int size = queue.size();
  8.             int left=Integer.MAX_VALUE;
  9.             int right = Integer.MIN_VALUE;
  10.             for(int i=0;i<size;i++){
  11.                 PositionNode cur = queue.poll();
  12.                 if(i==0)
  13.                     left = cur.index;
  14.                 if(i==size-1)
  15.                     right = cur.index;
  16.                 if(cur.root.left!=null)
  17.                     queue.offer(new PositionNode(cur.root.left,cur.index*2));
  18.                 if(cur.root.right!=null)
  19.                     queue.offer(new PositionNode(cur.root.right,cur.index*2+1));
  20.             }
  21.             max = Math.max(max,right-left+1);
  22.         } 
  23.         return max;
  24.     }
  25. }
  26.  
  27. class PositionNode{
  28.     TreeNode root;
  29.     int index;
  30.     PositionNode(){};
  31.     PositionNode(TreeNode root,int index){
  32.         this.root = root;
  33.         this.index = index;
  34.     }
  35. }

平衡二叉树

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

  1. class Solution {
  2.     public boolean isBalanced(TreeNode root) {
  3.         return getHeight(root)!=-1;
  4.     }
  5.  
  6.     public int getHeight(TreeNode root){
  7.         if(root==null) return 0;
  8.         int leftHeight = getHeight(root.left);
  9.         int rightHeight = getHeight(root.right);
  10.         if(leftHeight==-1||rightHeight==-1)
  11.             return -1;
  12.         return Math.abs(leftHeight-rightHeight)>1?-1:Math.max(leftHeight,rightHeight)+1;
  13.     }
  14. }

翻转二叉树

前序遍历递归翻转：

  1. class Solution {
  2.     public TreeNode invertTree(TreeNode root) {
  3.         if(root==null) return root;
  4.         //前序遍历，根节点直接反转左右子树
  5.         TreeNode left = root.left;
  6.         TreeNode right = root.right;
  7.         root.left = right;
  8.         root.right = left;  
  9.  
  10.         
  11.         //左右子树再进行反转
  12.         invertTree(root.left);
  13.         invertTree(root.right);
  14.         return root;
  15.     }
  16. }

层次遍历翻转：

  1. class Solution {
  2.     public TreeNode invertTree(TreeNode root) {
  3.         
  4.         Deque<TreeNode> queue = new LinkedList<>();
  5.         if(root != null) 
  6.             queue.offer(root);
  7.         while(!queue.isEmpty()){
  8.             int size = queue.size();
  9.             for(int i =0;i<size;i++){
  10.                 //反转当前节点
  11.                 TreeNode cur = queue.poll();
  12.                 TreeNode left = cur.left;
  13.                 TreeNode right = cur.right;
  14.                 cur.right = left;
  15.                 cur.left = right;
  16.                 //左右子树放入队列等待遍历
  17.                 if(cur.right!=null)
  18.                     queue.offer(cur.right);
  19.                 if(cur.left!=null)
  20.                     queue.offer(cur.left);
  21.             }
  22.         }
  23.         return root;
  24.     }
  25. }

二叉搜索树第K小元素

中序递归遍历

  1. class Solution {
  2.     int k;
  3.     int res;
  4.     public int kthSmallest(TreeNode root, int k) {
  5.         this.k=k;
  6.         inorder(root);
  7.         return res;
  8.  
  9.     }
  10.     public void inorder(TreeNode root){
  11.         //如果为空返回
  12.         if(root==null)
  13.             return ;
  14.         inorder(root.left);
  15.         //k减1，判断是否是第k个
  16.         k--;
  17.         if(k==0)
  18.             res = root.val;
  19.         inorder(root.right);
  20.     }
  21. }

二叉树展开为链表

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

递归：后序遍历

  1. class Solution {
  2.     TreeNode pre = null;
  3.     public void flatten(TreeNode root) {
  4.         if(root==null)
  5.             return ;
  6.         flatten(root.right);
  7.         flatten(root.left);
  8.         root.left = null;
  9.         root.right = pre;
  10.         pre = root;
  11.     }
  12. }

迭代：前序遍历

  1. class Solution {
  2.     public void flatten(TreeNode root) {
  3.         if(root==null)
  4.             return ;
  5.         Deque<TreeNode> stack = new LinkedList<>();
  6.         TreeNode pre = null;
  7.         stack.push(root);
  8.         while(!stack.isEmpty()){
  9.             TreeNode cur = stack.pop();
  10.             TreeNode left = cur.left;
  11.             TreeNode right = cur.right;
  12.             if(pre==null){
  13.                 pre = cur;
  14.                 pre.left = null;
  15.             }
  16.             else{
  17.                 pre.right = cur;
  18.                 pre.left = null;
  19.                 pre = pre.right;
  20.             }
  21.             if(right!=null)
  22.                 stack.push(right);
  23.             if(left!=null)
  24.                 stack.push(left);         
  25.         }
  26.         return ;
  27.     }
  28. }

二叉树展开为双向链表

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

  1. class Solution {
  2.     public Node treeToDoublyList(Node root) {
  3.         LinkedList<Node> stack = new LinkedList<>();
  4.         if(root==null){
  5.             return null;
  6.         }     
  7.         Node head = null;
  8.         Node pre = null;
  9.         stack.push(root);
  10.         while(!stack.isEmpty()){
  11.             Node cur = stack.pop();
  12.             if(cur!=null){
  13.                 if(cur.right!=null)
  14.                     stack.push(cur.right);
  15.                 stack.push(cur);
  16.                 stack.push(null);
  17.                 if(cur.left!=null)
  18.                     stack.push(cur.left);
  19.             }else{  
  20.                 cur = stack.pop();
  21.                 if(pre ==null){
  22.                     pre = cur;
  23.                     head = cur;
  24.                 }
  25.                 else{
  26.                     pre.right = cur;
  27.                     cur.left = pre;
  28.                     pre = pre.right;
  29.                 }
  30.             }
  31.         }
  32.         pre.right = head;
  33.         head.left = pre;
  34.         return head;
  35.     }
  36. }

树的遍历

1、递归前序遍历

  1. class Solution {
  2.     public List<Integer> preorderTraversal(TreeNode root) {
  3.         List<Integer> result = new ArrayList<>();
  4.         traversal(root,result);
  5.         return result;
  6.     }
  7.  
  8.     public void traversal(TreeNode root,List<Integer> result){
  9.         if(root==null){
  10.             return ;
  11.         }
  12.         result.add(root.val);
  13.         traversal(root.left,result);
  14.         traversal(root.right,result);
  15.     }
  16. }

2、非递归前序遍历

  1. class Solution {
  2.     public List<Integer> preorderTraversal(TreeNode root) {
  3.         List<Integer> result = new ArrayList<>();
  4.         Stack<TreeNode> stack = new Stack<>();
  5.         if(root!=null){
  6.             stack.push(root);
  7.         }
  8.         while(!stack.isEmpty()){
  9.             TreeNode node = stack.pop();
  10.             if(node!=null){
  11.                 if(node.right!=null){
  12.                     stack.push(node.right);
  13.                 }
  14.                 if(node.left!=null){
  15.                     stack.push(node.left);
  16.                 }
  17.                 stack.push(node);
  18.                 stack.push(null);
  19.             }else{
  20.                 TreeNode cur = stack.pop();
  21.                 result.add(cur.val);
  22.             }
  23.         }
  24.         return result;
  25.     }
  26. }

3、递归中序遍历

  1. class Solution {
  2.     public List<Integer> inorderTraversal(TreeNode root) {
  3.         List<Integer> result = new ArrayList<>();
  4.         traversal(root,result);
  5.         return result;
  6.     }
  7.  
  8.     public void traversal(TreeNode root,List<Integer> result){
  9.         if(root==null){
  10.             return ;
  11.         }
  12.         traversal(root.left,result);
  13.         result.add(root.val);
  14.         traversal(root.right,result);
  15.     }
  16. }

4、非递归中序遍历

  1. class Solution {
  2.     public List<Integer> inorderTraversal(TreeNode root) {
  3.         List<Integer> result = new ArrayList<>();
  4.         Stack<TreeNode> stack = new Stack<>();
  5.         if(root!=null){
  6.             stack.push(root);
  7.         }
  8.         while(!stack.isEmpty()){
  9.             TreeNode node = stack.pop();
  10.             if(node!=null){
  11.                 if(node.right!=null){
  12.                     stack.push(node.right);
  13.                 }
  14.                 stack.push(node);
  15.                 stack.push(null);
  16.                 if(node.left!=null){
  17.                     stack.push(node.left);
  18.                 }
  19.             }else{
  20.                 TreeNode cur = stack.pop();
  21.                 result.add(cur.val);
  22.             }
  23.         }
  24.         return result;
  25.     }
  26.  
  27. }

5、递归后序遍历

  1. class Solution {
  2.     public List<Integer> postorderTraversal(TreeNode root) {
  3.         List<Integer> result = new ArrayList<>();
  4.         traversal(root,result);
  5.         return result;
  6.     }
  7.     public void traversal(TreeNode root,List<Integer> result){
  8.         if(root==null){
  9.             return ;
  10.         }
  11.         traversal(root.left,result);
  12.         traversal(root.right,result);
  13.         result.add(root.val);
  14.     }
  15. }

6、非递归后序遍历

  1. class Solution {
  2.     public List<Integer> postorderTraversal(TreeNode root) {
  3.         List<Integer> result = new ArrayList<>();
  4.         Stack<TreeNode> stack = new Stack<>();
  5.         if(root!=null){
  6.             stack.push(root);
  7.         }
  8.         while(!stack.isEmpty()){
  9.             TreeNode node = stack.pop();
  10.             if(node!=null){
  11.                 stack.push(node);
  12.                 stack.push(null);
  13.                 if(node.right!=null){
  14.                     stack.push(node.right);
  15.                 }
  16.                 if(node.left!=null){
  17.                     stack.push(node.left);
  18.                 }
  19.             }else{
  20.                 TreeNode cur = stack.pop();
  21.                 result.add(cur.val);
  22.             }
  23.         }
  24.         return result;
  25.     }
  26. }

7、层次遍历

  1. class Solution {
  2.     public List<List<Integer>> levelOrder(TreeNode root) {
  3.         List<List<Integer>> result = new ArrayList<>();
  4.         Queue<TreeNode> queue = new LinkedList<>();
  5.         if(root!=null){
  6.             queue.offer(root);
  7.         }
  8.         while(!queue.isEmpty()){
  9.             List<Integer> levelResult = new ArrayList<>();
  10.             int size = queue.size();
  11.             for(int i =0;i<size;i++){
  12.                 TreeNode node = queue.poll();
  13.                 levelResult.add(node.val);
  14.                 if(node.left!=null){
  15.                     queue.offer(node.left);
  16.                 }
  17.                 if(node.right!=null){
  18.                     queue.offer(node.right);
  19.                 }
  20.             }
  21.             result.add(levelResult);
  22.         }
  23.         return result;
  24.     }
  25. }

另一棵树的子树

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

  1. class Solution {
  2.     public boolean isSubtree(TreeNode root, TreeNode subRoot) {
  3.         if(subRoot==null){
  4.             return true;
  5.         }
  6.         if(root==null){
  7.             return false;
  8.         }
  9.         return isEqual(root,subRoot) || isSubtree(root.left,subRoot) || isSubtree(root.right,subRoot);
  10.     }
  11.  
  12.     public boolean isEqual(TreeNode root1, TreeNode root2){
  13.         if(root1 == null && root2 ==null){
  14.             return true;
  15.         }
  16.         if(root1 == null || root2 ==null){
  17.             return false;
  18.         }
  19.         if(root1.val!=root2.val){
  20.             return false;
  21.         }
  22.         return isEqual(root1.left,root2.left)&&isEqual(root1.right,root2.right);
  23.     }
  24. }

树的子结构

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

  1. class Solution {
  2.     public boolean isSubStructure(TreeNode A, TreeNode B) {
  3.         return (A!=null&&B!=null)&& (isContain(A,B) || isSubStructure(A.left,B) || isSubStructure(A.right,B));
  4.     }
  5.     public boolean isContain(TreeNode A, TreeNode B){
  6.         if( B==null ){
  7.             return true;
  8.         }
  9.         if(A==null||A.val!=B.val){
  10.             return false;
  11.         }
  12.         return isContain(A.left,B.left)&&isContain(A.right,B.right);
  13.     }
  14. }

本文内容由网友自发贡献，转载请注明出处：【wpsshop博客】
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号