二叉树 6/21 91-95

1.找树左下角的值（ LeetCode 513 ）

层序遍历

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */
class Solution {
    
        public int findBottomLeftValue(TreeNode root) {
    
            Deque<TreeNode> deque = new LinkedList<>();
            deque.addLast(root);
            int ans = 0;
            while (!deque.isEmpty()){
    
                int num = deque.size();
                for (int i = 0; i < num; i++) {
    
                    TreeNode temp = deque.removeFirst();
                    if (i == 0)ans = temp.val;
                    if (temp.left != null)deque.addLast(temp.left);
                    if (temp.right != null)deque.addLast(temp.right);
                }
            }
            return ans;
        }
    }

2.修剪二叉搜索树（ LeetCode 669 ）

递归
利用二叉搜索树的性质

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */
class Solution {
    
        //返回修建后的根节点
        public TreeNode trimBST(TreeNode root, int low, int high) {
    
            if (root == null)return root;
            root.left = trimBST(root.left,low,high);//左节点置为处理好的节点
            root.right = trimBST(root.right,low,high);//右节点置为处理好的节点
            if (root.val < low){
    //情况一
                //root节点及左侧节点全部丢弃，因为root是二叉搜索树
                return root.right;
            }
            if (root.val > high){
    //情况二
                return root.left;
            }
            return root;
        }
    }

3.二叉搜索树的最近公共祖先（ LeetCode 235 ）

技巧

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */

 class Solution {
    
        TreeNode ans;
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    
            dfs(root,p,q);
            return ans;
        }
        public boolean dfs(TreeNode node,TreeNode p,TreeNode q){
    
            if (node == null)return false;
            boolean lb = dfs(node.left,p,q);
            boolean rb = dfs(node.right,p,q);
            if ((lb && rb) || ((lb || rb) && (p == node || q == node))){
    
                ans = node;
            }
            return lb || rb || p == node || q == node;
        }
    }

4.二叉搜索树的最小绝对差（ LeetCode 530 ）

中序遍历

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */
class Solution {
    
        List<Integer> list = new ArrayList<>();
        public int getMinimumDifference(TreeNode root) {
    
            dfs(root);
            int ans = Integer.MAX_VALUE;
            for (int i = 1; i < list.size(); i++) {
    
                ans = Math.min(ans,list.get(i) - list.get(i - 1));
            }
            return ans;
        }
        public void dfs(TreeNode node){
    
            if (node == null)return;
            dfs(node.left);
            list.add(node.val);
            dfs(node.right);
        }
    }

5.最大二叉树（ LeetCode 654 ）

递归

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */
class Solution {
    
        public TreeNode constructMaximumBinaryTree(int[] nums) {
    
            return build(nums,0,nums.length - 1);
        }
        public TreeNode build(int[] nums,int l,int r){
    
            if (l > r)return null;
            int max = nums[l];
            int maxidx = l;
            for (int i = l + 1; i <= r; i++) {
    
                if (nums[i] > max){
    
                    max = nums[i];
                    maxidx = i;
                }
            }
            TreeNode node = new TreeNode(max);
            node.left = build(nums,l,maxidx - 1);
            node.right = build(nums,maxidx + 1,r);
            return node;
        }
    }