LeetCode题解——树（三）

亦凉 2023-02-16 06:58 30阅读 0赞

### 文章目录 ###

*  前中后序遍历
 *   *  二叉树的前序遍历
     *   *  迭代
     *  二叉树的后序遍历
     *   *  迭代解法1
         *  迭代解法2
     *  二叉树的中序遍历
     *   *  迭代解法
 *  BST
 *   *  修剪二叉搜索树
     *   *  递归算法
     *  二叉搜索树中第K小的元素
     *   *  中序遍历
         *  递归解法
     *  把二叉搜索树转换为累加树
     *   *  递归解法
     *  二叉搜索树的最近公共祖先
     *   *  递归解法
     *  二叉树的最近公共祖先
     *   *  递归解法
         *   *  推荐阅读

# 前中后序遍历 #

## 二叉树的前序遍历 ##

给定一个二叉树，返回它的 前序 遍历。

示例:
    
    输入: [1,null,2,3]  
       1
        \
         2
        /
       3 
    
    输出: [1,2,3]
    进阶: 递归算法很简单，你可以通过迭代算法完成吗？

### 迭代 ###

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        
        public List<Integer> preorderTraversal(TreeNode root) {
        
            if (root == null) {
        
                return new LinkedList<>();
            }
            List<Integer> res = new LinkedList<>();
            Deque<TreeNode> stack = new LinkedList<>();
            stack.addFirst(root);
            while(!stack.isEmpty()) {
        
                TreeNode node = stack.removeFirst();
                res.add(node.val);
                if (node.right != null) {
        
                    stack.addFirst(node.right);
                }
                if (node.left != null) {
        
                    stack.addFirst(node.left);
                }
            }
            return res;
        }
    }

## 二叉树的后序遍历 ##

给定一个二叉树，返回它的 后序 遍历。

示例:
    
    输入: [1,null,2,3]  
       1
        \
         2
        /
       3 
    
    输出: [3,2,1]
    进阶: 递归算法很简单，你可以通过迭代算法完成吗？

### 迭代解法1 ###

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        
        public List<Integer> postorderTraversal(TreeNode root) {
        
            if (root == null) {
        
                return new LinkedList<>();
            }
            List<Integer> res = new ArrayList<>();
            Deque<TreeNode> stack = new LinkedList<>();
            stack.addFirst(root);
            while(!stack.isEmpty()) {
        
                TreeNode node = stack.removeFirst();
                res.add(node.val);
                if (node.left != null) {
        
                    stack.addFirst(node.left);
                }
                if (node.right != null) {
        
                    stack.addFirst(node.right);
                }
            }
            Collections.reverse(res);
            return res;
        }
    }

### 迭代解法2 ###

利用LinkedList的性质，可每次插入到链头，相当于翻转。

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        
        public List<Integer> postorderTraversal(TreeNode root) {
        
            if (root == null) {
        
                return new LinkedList<>();
            }
            LinkedList<Integer> res = new LinkedList<>();
            Deque<TreeNode> stack = new LinkedList<>();
            stack.addFirst(root);
            while(!stack.isEmpty()) {
        
                TreeNode node = stack.removeFirst();
                res.addFirst(node.val);
                if (node.left != null) {
        
                    stack.addFirst(node.left);
                }
                if (node.right != null) {
        
                    stack.addFirst(node.right);
                }
            }
            return res;
        }
    }

## 二叉树的中序遍历 ##

给定一个二叉树，返回它的中序 遍历。

示例:

输入: \[1,null,2,3\]  
1  
  
2  
/  
3

输出: \[1,3,2\]  
进阶: 递归算法很简单，你可以通过迭代算法完成吗？

### 迭代解法 ###

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        
        public List<Integer> inorderTraversal(TreeNode root) {
        
            if (root == null) {
        
                return new LinkedList<>();
            }
            List<Integer> res = new LinkedList<>();
            Deque<TreeNode> stack = new LinkedList<>();
            TreeNode node = root;
            while(node != null || !stack.isEmpty()) {
        
                while (node != null) {
        
                    stack.addLast(node);
                    node = node.left;
                }
                node = stack.removeLast();
                res.add(node.val);
                node = node.right;
            }
            return res;
        }
    }

# BST #

## 修剪二叉搜索树 ##

给定一个二叉搜索树，同时给定最小边界L 和最大边界 R。通过修剪二叉搜索树，使得所有节点的值在\[L, R\]中 (R>=L) 。你可能需要改变树的根节点，所以结果应当返回修剪好的二叉搜索树的新的根节点。

示例 1:
    
    输入: 
        1
       / \
      0   2
    
      L = 1
      R = 2
    
    输出: 
        1
          \
           2
    示例 2:
    
    输入: 
        3
       / \
      0   4
       \
        2
       /
      1
    
      L = 1
      R = 3
    
    输出: 
          3
         / 
       2   
      /
     1

### 递归算法 ###

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        
        public TreeNode trimBST(TreeNode root, int L, int R) {
        
            if (root == null) {
        
                return null;
            }
            if (root.val > R) {
        
                return trimBST(root.left, L, R);
            }
            if (root.val < L) {
        
                return trimBST(root.right, L, R);
            }
            root.left = trimBST(root.left, L, R);
            root.right = trimBST(root.right, L, R);
            return root;
        }
    }

## 二叉搜索树中第K小的元素 ##

给定一个二叉搜索树，编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。

说明：  
你可以假设 k 总是有效的，1 ≤ k ≤ 二叉搜索树元素个数。

示例 1:
    
    输入: root = [3,1,4,null,2], k = 1
       3
      / \
     1   4
      \
       2
    输出: 1
    示例 2:
    
    输入: root = [5,3,6,2,4,null,null,1], k = 3
           5
          / \
         3   6
        / \
       2   4
      /
     1
    输出: 3
    进阶：
    如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第 k 小的值，你将如何优化 kthSmallest 函数？

### 中序遍历 ###

/**
     * 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 {
        
        private int cnt = 0;
        private int val;
        public int kthSmallest(TreeNode root, int k) {
        
            inOrder(root, k);
            return val;
        }
        private void inOrder(TreeNode node, int k) {
        
            if (node == null) {
        
                return;
            }
            inOrder(node.left, k);
            cnt++;
            if (cnt == k) {
        
                val = node.val;
                return;
            }
            inOrder(node.right, k);
        }
    }

### 递归解法 ###

/**
     * 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 kthSmallest(TreeNode root, int k) {
        
            int leftCount = count(root.left);
            if (leftCount == k - 1) {
        
                return root.val;
            }
            if (leftCount > k - 1) {
        
                return kthSmallest(root.left, k);
            }
            return kthSmallest(root.right, k - leftCount - 1);
        }
        private int count(TreeNode node) {
        
            if (node == null) {
        
                return 0;
            }
            return 1 + count(node.left) + count(node.right);
        }
    }

## 把二叉搜索树转换为累加树 ##

给定一个二叉搜索树（Binary Search Tree），把它转换成为累加树（Greater Tree)，使得每个节点的值是原来的节点值加上所有大于它的节点值之和。

例如：
    
    输入: 原始二叉搜索树:
                  5
                /   \
               2     13
    
    输出: 转换为累加树:
                 18
                /   \
              20     13

### 递归解法 ###

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        
        private int sum = 0;
        public TreeNode convertBST(TreeNode root) {
        
            traver(root);
            return root;
        }
        private void traver(TreeNode node) {
        
            if (node == null) {
        
                return;
            }
            traver(node.right);
            sum += node.val;
            node.val = sum;
            traver(node.left);
        }
    }

## 二叉搜索树的最近公共祖先 ##

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

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

例如，给定如下二叉搜索树: root = \[6,2,8,0,4,7,9,null,null,3,5\]

![format_png][]

示例 1:
    
    输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
    输出: 6 
    解释: 节点 2 和节点 8 的最近公共祖先是 6。
    示例 2:
    
    输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
    输出: 2
    解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。
     
    
    说明:
    
    所有节点的值都是唯一的。
    p、q 为不同节点且均存在于给定的二叉搜索树中。

### 递归解法 ###

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        
            int val = root.val;
            if (val > p.val && val > q.val) {
        
                return lowestCommonAncestor(root.left, p, q);
            }
            if (val < p.val && val < q.val) {
        
                return lowestCommonAncestor(root.right, p, q);
            }
            return root;
        }
    }

## 二叉树的最近公共祖先 ##

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

例如，给定如下二叉树: root = \[3,5,1,6,2,0,8,null,null,7,4\]

![format_png 1][]

示例 1:
    
    输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
    输出: 3
    解释: 节点 5 和节点 1 的最近公共祖先是节点 3。
    示例 2:
    
    输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
    输出: 5
    解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。
     
    
    说明:
    
    所有节点的值都是唯一的。
    p、q 为不同节点且均存在于给定的二叉树中。

### 递归解法 ###

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        
            if (root == null || root == p || root == q) {
        
                return root;
            }
            TreeNode left = lowestCommonAncestor(root.left, p, q);
            TreeNode right = lowestCommonAncestor(root.right, p, q);
            return left == null ? right : right == null ? left : root;
        }
    }

--------------------

#### 推荐阅读 ####

*  [机器学习资料汇总][Link 1]
 *  [吴恩达《机器学习》视频、作业、源码][Link 2]
 *  [106页《Python进阶》中文版正式发布][106_Python]
 *  [李航《统计学习方法》第二版完整课件][Link 3]
 *  [机器学习数学全书，1900页PDF下载][1900_PDF]

--------------------

![format_png 2][]

[format_png]: https://imgconvert.csdnimg.cn/aHR0cDovL3dhcmRzZXB0ZW1iZXIuY2x1Yi8yMDIwMDYwOTEyNTIyMC5wbmc?x-oss-process=image/format,png
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cDovL3dhcmRzZXB0ZW1iZXIuY2x1Yi8yMDIwMDYwOTEzMDYyOC5wbmc?x-oss-process=image/format,png
[Link 1]: https://mp.weixin.qq.com/s/3nOkk_Yt9D7Qp1WaWEjyZQ
[Link 2]: https://mp.weixin.qq.com/s/dErZNtBYbVA7ItPm7T_HIw
[106_Python]: https://mp.weixin.qq.com/s/_WEuuxj-QgihijjLz7NJ9g
[Link 3]: https://mp.weixin.qq.com/s/xah47OWuu8ahAUa1aFFo4Q
[1900_PDF]: https://mp.weixin.qq.com/s/9BuyhdwuHiHH3ksVUe44ZQ
[format_png 2]: https://imgconvert.csdnimg.cn/aHR0cDovL3dhcmRzZXB0ZW1iZXIuY2x1Yi9Gc2lzMkxhbzF6UkEtUnBic1RFREEwX3owNHdi?x-oss-process=image/format,png