LeetCode：二叉树

大大源码 • 2023年4月13日 pm9:04 • 未分类

二叉树锯齿形遍历

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，不如取0
        int left = Math.max(0,inOrder(root.left));
        //如果右边来的路径小于0，不如取0
        int 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 here
        return 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){          
            //左孩子节点加入path
            path.offer(root.left.val);
            traverl(root.left,targetSum-root.left.val);
            //左孩子节点弹出path
            path.pollLast();
        }
        //遍历右子树
        if(root.right!=null){
            //右孩子节点加入path
            path.offer(root.right.val);
            traverl(root.right,targetSum-root.right.val);
            //右孩子节点加入path
            path.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();
            //每层遍历完之后 深度加1
            while (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);
    }
}

原文链接：https://blog.csdn.net/sfklyqh/article/details/122353990

THE END

asp.net2.0：扩展ImageButton控件定制自己需要的功能

< <上一篇

Hadoop完全分布式安装（HA、Yarn、ZKFC、flumeGanglia、sqoop一步到位）

下一篇>>

大大搜源码

搜索内容