Easy

二叉树的深度104. Maximum Depth of Binary Tree

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def maxDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        left = 0
        right = 0
        if root is  None:
            return 0
        else:
            if root.left is not None:
                left = self.maxDepth(root.left)
            if root.right is not None:
                right = self.maxDepth(root.right)
        return 1+max(left,right)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

简单的解法：

def depth(root):
     if root==None:
          return 0
      return 1+max(depth(root.left),depth(root.right))
        
1
2
3
4
5

直径类型题

二叉树的直径 543. Diameter of Binary Tree

直径的定义是二叉树上任意两节点之间的无向距离

注意：这条路不一定经过根节点

class Solution {
    int max = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        if (root == null) {
            return 0;
        }
        dfs(root);
        return max;
    }
    
    private int dfs(TreeNode root) {
        if (root.left == null && root.right == null) {
            return 0;
        }
        int leftSize = root.left == null? 0: dfs(root.left) + 1;
        int rightSize = root.right == null? 0: dfs(root.right) + 1;
        max = Math.max(max, leftSize + rightSize);
        return Math.max(leftSize, rightSize);
    }  
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

二叉树中最大路径和 124. Binary Tree Maximum Path Sum

和上题最长路径一样，也可以不经过根节点

虽然是Hard但解法和本题一毛一样～～ 唯一的区别是：不是求边长，而是路径上节点的value之和，因为节点的value可能是负数，因此求左孩子右孩子的时候要int leftSum = Math.max(0, dfs(root.left));舍弃掉负数的结果。

class Solution {
    int max = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        dfs(root);
        return max;
    }

    private int dfs(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftSum = Math.max(0, dfs(root.left)); // 和上题唯一的区别在这里，如果左右孩子的结果是负数的话就舍弃。
        int rightSum = Math.max(0, dfs(root.right));
        max = Math.max(max, leftSum + rightSum + root.val);
        return Math.max(leftSum, rightSum) + root.val;
    }
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

最长同值路径 687. Longest Univalue Path

找出由相同数组成的最大路径长度

又是和最大直径的题类似，遍历所有节点，以每个节点为中心点求最长路径（左右子树的边长之和），更新全局max。唯一的区别是，求出了左孩子的边长leftSize后，如果左孩子和当前节点不同值的话，那要把leftSize重新赋值成0。

class Solution {
    int max = 0;
    public int longestUnivaluePath(TreeNode root) {
        if (root == null) {
            return 0;
        }
        dfs(root);
        return max;
    }

    public int dfs(TreeNode root){
        if(root==null) return 0;
        int l = 0, r = 0;
        l = dfs(root.left);
        r = dfs(root.right);
        if(root.left!=null){
            if(root.left.val==root.val){
                l++;
            }
            else l = 0;
        }
        if(root.right!=null){
            if(root.right.val==root.val){
                r++;
            }
            else r = 0;
        }
        max = Math.max(l+r,max);
        return Math.max(l,r);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

二叉树的遍历

前序遍历：根左右

class Solution(object):
    def preorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        res = []
        def traversal(root):
            if root == None:
                return
            res.append(root.val) # 前序
            traversal(root.left)    # 左
            traversal(root.right)   # 右
        traversal(root)
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

中序遍历：左根右

在二叉平衡树下，中序遍历返回序列是从小到大排序的

class Solution(object):
    def inorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        res = []
        def ff(root):
            if root == None:
                return 
            ff(root.left)
            res.append(root.val)
            ff(root.right)
            return res
        
        return ff(root)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

层序遍历

class Solution(object):
    def levelOrder(self, root):
        if root == None:
            return []
        queue = [root]
        res = []
        while queue:
            temp = []
            for i in range(len(queue)):
                r = queue.pop(0)
                temp.append(r.val)
                if r.left!=None:
                    queue.append(r.left)
                if r.right!=None:
                    queue.append(r.right)
            res.append(temp)
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

自底向上的层序遍历

思路：层序遍历后得到的列表，进行倒置即可，即res.reverse()

class Solution(object):
    def levelOrderBottom(self, root):
        if root == None:
            return []
        queue = [root]
        res = []
        while queue:
            temp = []
            for i in range(len(queue)):
                r = queue.pop(0)
                temp.append(r.val)
                if r.left!=None:
                    queue.append(r.left)
                if r.right!=None:
                    queue.append(r.right)
            res.append(temp)
        res.reverse()
        return res   
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

递增顺序搜索树

• 方法一：中序遍历之后生成新的树

class Solution(object):
    def increasingBST(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        def medium(root,res):
            if root==None:
                return 
            medium(root.left,res)
            res.append(root.val)
            medium(root.right,res)
        
        res = []
        medium(root,res)

        # 新建二叉树
        rroot = TreeNode(-1)
        curNode = rroot
        for val in res:
            curNode.right = TreeNode(val)
            curNode = curNode.right
        
        return rroot.right
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

• 方法二：在中序遍历的过程中改变节点指向

当我们遍历到一个节点时，把它的左孩子设为空，并将其本身作为上一个遍历到的节点的右孩子。

class Solution {
    private TreeNode resNode;

    public TreeNode increasingBST(TreeNode root) {
        TreeNode dummyNode = new TreeNode(-1);
        resNode = dummyNode;
        inorder(root);
        return dummyNode.right;
    }

    public void inorder(TreeNode node) {
        if (node == null) {
            return;
        }
        inorder(node.left);

        // 在中序遍历的过程中修改节点指向
        resNode.right = node;
        node.left = null;
        resNode = node;

        inorder(node.right);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

左叶子之和

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

二叉树的 最底层 最左边 节点的值

- 层次遍历

class Solution {
    public int findBottomLeftValue(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()){
            root = queue.poll();
            if (root.right != null) queue.add(root.right);
            if (root.left != null) queue.add(root.left);
        }
        return root.val;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

二叉树最近公共祖先

class Solution(object):
    def lowestCommonAncestor(self, root, p, q):
        """
        :type root: TreeNode
        :type p: TreeNode
        :type q: TreeNode
        :rtype: TreeNode
        """
        if root == None:
            return None
        if root==p or root==q:
            return root
        left =self.lowestCommonAncestor(root.left,p,q)
        right = self.lowestCommonAncestor(root.right,p,q)

        if left!=None and right!=None:
            return root
        if left!=None:
            return left
        if right!=None:
            return right
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

二叉树的镜像 / 翻转二叉树

题解思路：从下到上交换左右两子树

class Solution(object):
    def mirrorTree(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        if root == None :
            return root
        temp = root.left
        root.left = self.mirrorTree(root.right)
        root.right = self.mirrorTree(temp)
        return root
1
2
3
4
5
6
7
8
9
10
11
12

class Solution(object):
    def invertTree(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        if root == None:
            return 
        if root.left != None or root.right!=None:
            temp = root.left
            root.left = root.right
            root.right = temp

        self.invertTree(root.left)
        self.invertTree(root.right)
        return root
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

对称二叉树

判断二叉树是否对称

容易错的点：不能用层次遍历，若出现[1,2,2,null,3,null,3]的情况，第三层容易写成[3,3]，这样就容易判断为true。

得用递归做

class Solution(object):
    def isSymmetric(self, root):
        if root == None:
            return True

        def issame(root1,root2):
            if root1==None and root2==None:
                return True
            elif root1!=None and root2!=None:
                if root1.val != root2.val:
                    return False
                else:
                    return issame(root1.left,root2.right) and issame(root1.right,root2.left)
            else:
                return False
        return issame(root,root)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

合并二叉树

class Solution(object):
    def mergeTrees(self, root1, root2):
        """
        :type root1: TreeNode
        :type root2: TreeNode
        :rtype: TreeNode
        """
        if root1==None:
            return root2
        if root2==None:
            return root1
        root1.val = root1.val+root2.val
        root1.left = self.mergeTrees(root1.left,root2.left)
        root1.right = self.mergeTrees(root1.right,root2.right)
        
        return root1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

叶子结点相同的树

class Solution(object):
    def leafSimilar(self, root1, root2):
        """
        :type root1: TreeNode
        :type root2: TreeNode
        :rtype: bool
        """

        def leaf(root,res):
            if root==None:
                return 
            if root.left == None and root.right==None:
                res.append(root.val)
            leaf(root.left,res)
            leaf(root.right,res)
        
        if root1==None and root2==None:
            return True
        elif root1!=None and root2!=None:
            res1,res2=[],[]
            leaf(root1,res1)
            leaf(root2,res2)
            return res1==res2
        else:
            return False
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

检查平衡性 110. Balanced Binary Tree

class Solution(object):
    def isBalanced(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        def depth(root):
            if root==None:
                return 0
            return 1+max(depth(root.left),depth(root.right))
        
        if root==None:
            return True
        if abs(depth(root.left)- depth(root.right))<=1:
            return self.isBalanced(root.left) and self.isBalanced(root.right)
        else:
            return False
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

java

class Solution {
    public boolean isBalanced(TreeNode root) {
        if(root==null) return true;
        if(Math.abs(maxDepth(root.left)-maxDepth(root.right))>1) return false;
        else{
            return isBalanced(root.left)&isBalanced(root.right);
        }


    }
    public int maxDepth(TreeNode root) {
        if(root==null) return 0;
        return 1+Math.max(maxDepth(root.left),maxDepth(root.right));
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

653. 两数之和 IV - 输入 BST

• 方法一：深度优先搜索 + 哈希表

在递归搜索过程中记录下相应的节点值（使用 Set 集合），如果在遍历某个节点 x时发现集合中存在 k−x.val，说明存在两个节点之和等于 k，返回 True，若搜索完整棵树都没有则返回False。

class Solution {
    Set<Integer> set = new HashSet<>();
    public boolean findTarget(TreeNode root, int k) {
        if (root == null) return false;
        if (set.contains(k - root.val)) return true;
        set.add(root.val);
        return findTarget(root.left, k) || findTarget(root.right, k);
    }
}
1
2
3
4
5
6
7
8
9

• 方法二：双指针 + BST 中序遍历

首先，定义leftStk和rightStk 表示从根节点开始，一直往左走的点，以及一直往右走的点。由二叉搜索树的定义，一直往左走就会变小，所以leftStk数组中的值从大到小排序，而rightStk 则是从小到大。

接着，分别取最左端和最右端的，如果和小于k，则说明左边的数取小了，因此，我们要把left=leftStk.pop()等于次小的，接着还要把新取的left点的右子树加入到leftStk中去，因为这些是次小的。

class Solution:
    def findTarget(self, root: Optional[TreeNode], k: int) -> bool:
        left, right = root, root
        leftStk, rightStk = [left], [right]
        while left.left:
            left = left.left
            leftStk.append(left)
        while right.right:
            right = right.right
            rightStk.append(right)
        while left != right:
            sum = left.val + right.val
            if sum == k:
                return True
            if sum < k:
                left = leftStk.pop()
                node = left.right
                while node:
                    leftStk.append(node)
                    node = node.left
            else:
                right = rightStk.pop()
                node = right.left
                while node:
                    rightStk.append(node)
                    node = node.right
        return False
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

创建二叉树结构字符

class Solution(object):
    def tree2str(self, root):
        """
        :type root: TreeNode
        :rtype: str
        """
        string = ""
        string = []
        def pre(root,string):
            if root== None:
                return 
            #string.append(str(root.val)) 
            if root.left!= None and root.right !=None:
                string.append(str(root.val))
                string.append("(")
                pre(root.left,string)
                string.append(")")
                string.append("(")
                pre(root.right,string)
                string.append(")")
                
            if root.left!= None and root.right ==None:
                string.append(str(root.val))
                string.append("(")
                pre(root.left,string)
                string.append(")")
                
            if root.left== None and root.right !=None:
                string.append(str(root.val))
                string.append("()")
                string.append("(")
                pre(root.right,string)
                string.append(")")
                
            if root.left== None and root.right ==None:
                string.append(str(root.val)) 

        pre(root,string)
        
        
        return "".join(string)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

538. 把二叉搜索树转换为累加树

• 思路：先遍历到最右的右子节点，然后值等于自己，在往回遍历根节点，根节点值等于右子树+根节点值，在遍历到左子树

遍历顺序：右→根→左

class Solution {
    int sum = 0;

    public TreeNode convertBST(TreeNode root) {
        if (root != null) {
            convertBST(root.right);
            sum += root.val;
            root.val = sum;
            convertBST(root.left);
        }
        return root;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

二叉树的所有路径

class Solution:
    def binaryTreePaths(self, root):
        """
        :type root: TreeNode
        :rtype: List[str]
        """
        path = ''
        paths = []
        def search(root, path, paths):
            if root == None:
                return 
            else:
                path += str(root.val)
                if root.left == None and root.right == None:
                    paths.append(path)
                else: 
                    path += '->'
                    search(root.left, path, paths)
                    search(root.right, path, paths)
        search(root, path, paths)

        return paths
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

N叉树

N叉树的深度

"""
# Definition for a Node.
class Node(object):
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children
"""

class Solution(object):
    def maxDepth(self, root):
        """
        :type root: Node
        :rtype: int
        """
        if root == None:
            return 0
        
        depth = 0
        for child in root.children:
            depth = max(depth,self.maxDepth(child))

        return depth+1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

N叉树的前序遍历

class Solution(object):
    def preorder(self, root):
        """
        :type root: Node
        :rtype: List[int]
        """
        if root is None:
            return []
        
        stack, output = [root, ], []            
        while stack:
            root = stack.pop()
            output.append(root.val)
            stack.extend(root.children[::-1])
            #[::-1]表示逆序
          
        return output
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

N叉树的后序遍历

class Solution(object):
    def postorder(self, root):
        """
        :type root: Node
        :rtype: List[int]
        """
        if root is None:
            return []
        
        stack, output = [root, ], []
        while stack:
            root = stack.pop()
            if root is not None:
                output.append(root.val)
            for c in root.children:
                stack.append(c)
                
        return output[::-1]



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution(object):
    def postorder(self, root):
        """
        :type root: Node
        :rtype: List[int]
        """
        if root == None:
            return []
        inverse = []
        def last(root,inverse):
            # 先放叶子，再放根
            if root.children == None:
                inverse.append(node.val)
            else:
                for child in root.children:
                    last(child,inverse)
                    inverse.append(child.val)
        last(root,inverse)
        inverse.append(root.val)
    
        return inverse
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

判断一棵树是否为其子树

• 思路：一个节点匹配一次，看该节点是否和subroot的首节点一样，一样的话往下检查，直到不一样就返回false,一样就返回true，这个函数叫check函数。

左边的数中每个节点都要遍历到，每个节点都会有个bool值，用dfs遍历，然后这些bool值取或

class Solution {
    public boolean isSubtree(TreeNode s, TreeNode t) {
        return dfs(s, t);
    }

    public boolean dfs(TreeNode s, TreeNode t) {
        if (s == null) {
            return false;
        }
        return check(s, t) || dfs(s.left, t) || dfs(s.right, t);
    }

    public boolean check(TreeNode s, TreeNode t) {
        if (s == null && t == null) {
            return true;
        }
        if (s == null || t == null || s.val != t.val) {
            return false;
        }
        return check(s.left, t.left) && check(s.right, t.right);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

第二种方法：将空的右子树标记为null，前序遍历得到字符串，判断字符串是否为子字符串，用KMP算法

Medium

删除节点

给定一个整数二叉树（所有节点值不同）和一些整数，求删掉这些整数对应的节点后，剩余的子树。

首先，定义del函数，用后序遍历，即左-右-根的遍历方式。如果node是我们要删除的点，就返回null，否则返回本身。

同时新建一个list数组，用于存放被分割的点，一开始存放初始点root，如果接下去遍历的时候root需要被删除，那么它的非空左右点就是分割点，需要被放入

/**
* 定义：
* 删除以node为根的树中，结点值出现在delete中的结点,更新结果集list，并返回删除后新的根节点。
*/
TreeNode del(TreeNode node, Set<Integer> delete, List<TreeNode> list);
1
2
3
4
5

    TreeNode del(TreeNode node, Set<Integer> delete, List<TreeNode> list){
        if(node == null) return null; // base case
        // 先递归左右子树
        node.left = del(node.left, delete, list);
        node.right = del(node.right, delete,list);
        
        if(delete.contains(node.val)){ // 当node结点需要被删掉时,更新结果集
            if(node.left != null){ 
                list.add(node.left);
            }
            if(node.right != null){ 
                list.add(node.right);
            }
            // 如果结果集里已经包含node为根的树，就把结果集里的node删掉
            if(list.contains(node)){
                list.remove(node);
            }
            // 将node置为null，等于删除掉了
            return null;
        }
        return node;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

整体代码

    public List<TreeNode> delNodes(TreeNode root, int[] to_delete) {
        List<TreeNode> list = new LinkedList<>();
        Set<Integer> set = new HashSet<>();
        // 将delete转换为set方便进行判断
        for(int num : to_delete){
            set.add(num);
        }
        // 如果什么都不需要删掉，那么结果集中应该包含原本这棵树
        list.add(root);
        del(root, set, list);
        return list;
    }

    TreeNode del(TreeNode node, Set<Integer> delete, List<TreeNode> list){
        if(node == null) return null;
        node.left = del(node.left, delete, list);
        node.right = del(node.right, delete,list);
        if(delete.contains(node.val)){
            if(node.left != null){
                list.add(node.left);
            }
            if(node.right != null){
                list.add(node.right);
            }
            if(list.contains(node)){
                list.remove(node);
            }
            return null;
        }
        return node;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

二叉搜索树

不同的二叉搜索树

class Solution(object):
    def numTrees(self, n):
        """
        :type n: int
        :rtype: int
        """
        
        G = [0]*(n+1)
        G[0], G[1] = 1, 1

        for i in range(2, n+1):
            for j in range(1, i+1):
                G[i] += G[j-1] * G[i-j]

        return G[n]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

打印出所有不同的二叉搜索树

class Solution(object):
    def generateTrees(self, n):
        """
        :type n: int
        :rtype: List[TreeNode]
        """
        def G(start,end):
            if start>end :
                return [None]
            res = []
            for i in range(start,end+1):
                # 左右子树有好多种可能性，挑一个拼在节点上
                leftTrees = G(start, i - 1)
                rightTrees = G(i + 1, end)
                for left in leftTrees:
                    for right in rightTrees:
                        root = TreeNode(i)
                        root.left = left
                        root.right = right
                        res.append(root)
            return res
        return G(1,n) if n else []
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

验证是否为搜索树

注意：即使是下面这种情况也是错的，因为右子树含有3,3比根节点5大

• 方法一：中序遍历，看是否从小到大排列

class Solution(object):
	  # 中序遍历
    def search(self, root):
        if root == None:
            return []
        return self.search(root.left) + [root.val] + self.search(root.right)
    
    def isValidBST(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        nums = self.search(root)
        return sorted(list(set(nums))) == nums
1
2
3
4
5
6
7
8
9
10
11
12
13
14

• 方法二：遍历节点，判断节点是否在(lower,uper)中

class Solution(object):
    def isValidBST(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """

        def subtree(root,lower = float('-inf'), upper = float('inf')):
            if root == None:
                return True
            if root.val > lower and root.val<upper:
                return subtree(root.left,lower,root.val) and subtree(root.right,root.val,upper)
            else:
                return False
        return subtree(root,float('-inf'),float('inf'))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

恢复二叉搜索树

-方法一：中序遍历获得两个错误节点

如何获得？正确的树中序遍历得到的应该是从小到大排序，因此我们可以知道

• 错误节点1：中序遍历下，前节点值>该节点值，这个前节点就是错误节点
• 错误节点2: 最后一个使得前节点值>该节点值的节点

class Solution(object):
    def recoverTree(self, root):
        self.t1 = None
        self.t2 = None
        self.pre = None
    
        def medium_search(root):
            if root==None:
                return
            medium_search(root.left)
            
            if self.pre!=None and self.pre.val>root.val:
                if  self.t1==None:
                    self.t1 = self.pre
                self.t2 = root
            self.pre = root
            medium_search(root.right)
        
        medium_search(root)
        temp = self.t1.val
        self.t1.val = self.t2.val
        self.t2.val = temp

        return root
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

-方法二：中序遍历节点存列表，再找到不是顺序的两个值交换

错误节点的定义与方法一相同

class Solution(object):
    def recoverTree(self, root):
        nodes = []
        # 中序遍历二叉树，并将遍历的结果保存到list中        
        def dfs(root):
            if not root:
                return
            dfs(root.left)
            nodes.append(root)
            dfs(root.right)
        dfs(root)
        x = None
        y = None
        pre = nodes[0]
        # 扫面遍历的结果，找出可能存在错误交换的节点x和y
        for i in xrange(1,len(nodes)):
            if pre.val>nodes[i].val:
                y=nodes[i]
                if not x:
                    x = pre
            pre = nodes[i]
        # 如果x和y不为空，则交换这两个节点值，恢复二叉搜索树 
        if x and y:
            x.val,y.val = y.val,x.val
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

修剪二叉搜索树 669. Trim a Binary Search Tree

当 node.val > R\text{node.val > R}node.val > R，那么修剪后的二叉树必定出现在节点的左边。

类似地，当 node.val < L\text{node.val < L}node.val < L，那么修剪后的二叉树出现在节点的右边。否则，我们将会修剪树的两边

class Solution {
    public TreeNode trimBST(TreeNode root, int L, int R) {
        if (root == null) return root;
        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;
    }
}
1
2
3
4
5
6
7
8
9
10
11

构造二叉树

• 本质：寻找可以将左右子树划分开的根节点，获得左右子树的位置

前序+中序构造二叉树

class Solution(object):
    def buildTree(self, preorder, inorder):
        n = len(preorder)
        # 中序遍历中根节点位置存储为字典,{'节点值'：中序遍历序列中位置}
        index = {element: i for i, element in enumerate(inorder)}

        def pre_in_buildTree(pre_left,pre_right,in_left,in_right):
            if pre_left>pre_right:
                return None
            pre_root = pre_left
            root_val = preorder[pre_root]
            in_root = index[root_val]

            root = TreeNode(root_val)

            # 构造左子树
            size_left = in_root-in_left
            pre_l_left = pre_left+1
            pre_l_right = pre_left+size_left
            in_l_left = in_left
            in_l_right = in_root-1
            root.left = pre_in_buildTree(pre_l_left,pre_l_right,in_l_left,in_l_right)

            # 构造右子树
            size_right = in_right - in_root
            pre_r_left = pre_l_right+1
            pre_r_right = pre_right
            in_r_left = in_root+1
            in_r_right = in_right
            root.right = pre_in_buildTree(pre_r_left,pre_r_right,in_r_left,in_r_right)

            return root
        return pre_in_buildTree(0, n - 1, 0, n - 1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

中序+后序构造二叉树

与前序+中序类似，关键是要找出根节点和左右子树在中序和后序中的位置

class Solution(object):
    def buildTree(self, inorder, postorder):
        index = {value:key for key,value in enumerate(inorder)}
        
        def post_in_buildTree(post_left, post_right, in_left, in_right):
            
            if post_left>post_right or (in_left>in_right):
                return None
            post_root = post_right
            root_val = postorder[post_root]
            in_root = index[root_val]
            root = TreeNode(root_val)
            # 构造左子树
            size_left = in_root - in_left
            in_l_right = in_root-1
            in_l_left = in_left
            post_l_left = post_left
            post_l_right = post_left+size_left-1
            root.left = post_in_buildTree(post_l_left, post_l_right, in_l_left, in_l_right)

            #构造右子树
            post_r_left = post_left+size_left
            post_r_right = post_right-1
            in_r_left = in_root + 1
            in_r_right = in_right
            root.right = post_in_buildTree(post_r_left, post_r_right, in_r_left, in_r_right)

            return root
        
        return post_in_buildTree(0, len(postorder)-1, 0, len(postorder)-1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

前序+后序构造二叉树

给定两个整数数组，preorder 和 postorder ，其中 preorder 是一个具有 无重复 值的二叉树的前序遍历，postorder 是同一棵树的后序遍历，重构并返回二叉树。

如果存在多个答案，您可以返回其中 任何 一个。

思路：

• 与中序遍历不同，前序和后序遍历根节点都在最前，不将左右子树划分开来。
• 前序遍历中，左子树根节点位置是pre[pre_left+1]，在后序遍历中找到这个位置，就是切分左右子树的位置。
• 需要注意：前序遍历中，左子树最右侧区间范围不要超过原区间pre_right

class Solution(object):
    def constructFromPrePost(self, preorder, postorder):
        index = {value:key for key,value in enumerate(postorder)}
        def pre_post_buildTree(pre_left,pre_right,post_left,post_right):
            if pre_left>pre_right or post_left>post_right:
                return None
            
            val = preorder[pre_left]
            root = TreeNode(val)
            if pre_left<len(preorder)-1:
                post_l_right = index[preorder[pre_left+1]]
                post_l_left = post_left
                size_left = post_l_right-post_l_left
                pre_l_left = pre_left+1
                pre_l_right = min(pre_l_left+size_left,pre_right)

                post_r_left = post_l_right+1
                post_r_right = post_right
                pre_r_left = pre_l_right+1
                pre_r_right = pre_right

                root.left = pre_post_buildTree(pre_l_left,pre_l_right,post_l_left,post_l_right)
                root.right = pre_post_buildTree(pre_r_left,pre_r_right,post_r_left,post_r_right)

            return root
        return pre_post_buildTree(0,len(preorder)-1,0,len(preorder)-1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

将有序数组转为高度平衡的二叉搜索树

高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。注意：二叉树不唯一，随便哪个都算对

• 自己思路
  通过前序和中序遍历构造二叉树

1. 中序：二叉搜索树中序遍历返回的就是有序数组，因此输入的有序遍历实际上就是我们要的中序遍历数组
2. 前序：根左右，由搜索二叉树性质看，左<根＜右，又要求左右子树高度差不超过1。因此，首先，有序数组中间的是根节点，加入到前序遍历中。其次，左右两边为左子和右子树，再将子树进行对半划分，中间为根节点，左右两半为左子右子…以此类推

class Solution(object):
    def sortedArrayToBST(self, nums):
        import math
        inoder = nums
        n = len(nums)
        preorder = []
        index = {value:key for key,value in enumerate(inoder)}

        # 得到前序遍历，对半分最中间的为根节点
        def get_medium(nums,n,preorder):
            med = int(math.ceil(n/2))
            if n>0:
                preorder.append(nums[med])
                get_medium(nums[:med],len(nums[:med]),preorder)
                get_medium(nums[med+1:],len(nums[med+1:]),preorder)
        # 前序+中序构造二叉树
        def pre_in_buildTree(pre_left,pre_right,in_left,in_right):
            if pre_left>pre_right:
                return None
            pre_root = pre_left
            root_val = preorder[pre_root]
            in_root = index[root_val]

            root = TreeNode(root_val)

            # 构造左子树
            size_left = in_root-in_left
            pre_l_left = pre_left+1
            pre_l_right = pre_left+size_left
            in_l_left = in_left
            in_l_right = in_root-1
            root.left = pre_in_buildTree(pre_l_left,pre_l_right,in_l_left,in_l_right)

            # 构造右子树
            size_right = in_right - in_root
            pre_r_left = pre_l_right+1
            pre_r_right = pre_right
            in_r_left = in_root+1
            in_r_right = in_right
            root.right = pre_in_buildTree(pre_r_left,pre_r_right,in_r_left,in_r_right)

            return root
        
        get_medium(nums,n,preorder)
        
        return pre_in_buildTree(0,n-1,0,n-1)
        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

• 题解：直接用中序遍历即可

中序遍历，总是选择中间位置左边的数字作为根节点（也可以选择中间位置右边的）

class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
        def helper(left, right):
            if left > right:
                return None

            # 总是选择中间位置左边的数字作为根节点
            mid = (left + right) // 2 #表示整除

            root = TreeNode(nums[mid])
            root.left = helper(left, mid - 1)
            root.right = helper(mid + 1, right)
            return root

        return helper(0, len(nums) - 1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

有序链表转换高度平衡的二叉搜索树

思路：把链表转为数组，然后与上题一致

class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution(object):
    def sortedListToBST(self, head):
        inorder = []
        def get_list(head,inorder):
            p = head
            while p:
                inorder.append(p.val)
                p = p.next

        def get_tree(inorder,left,right):
            if left>right:
                return None
            mid = (left+right)//2
            root = TreeNode(inorder[mid])
            root.left = get_tree(inorder,left,mid-1)
            root.right = get_tree(inorder,mid+1,right)
            return root

        get_list(head,inorder)

        return get_tree(inorder,0,len(inorder)-1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

二叉树的右视图

• 方法（自己）：层序遍历

class Solution(object):
    def rightSideView(self, root):
        if root == None:
            return []
        res = []
        queue = [root]
        # 层序遍历，找到每行最后一个
        while queue:
            temp = []
            size = len(queue)
            for i in range(size):
                node = queue.pop(0)
                temp.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            if len(temp)>0:
                res.append(temp[len(temp)-1]) 
            
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

• 方法：深度优先搜索

思路： 我们按照 「根结点 -> 右子树 -> 左子树」 的顺序访问，就可以保证每层都是最先访问最右边的节点的。

class Solution(object):
    def rightSideView(self, root):
        res = []

        def dfs(root,depth,res):
            if root == None:
                return 
            # 每一层放一个进入res,判断这层有没有被放进去
            if depth == len(res):
                res.append(root.val)
            depth += 1
            dfs(root.right,depth,res)
            dfs(root.left,depth,res)
        dfs(root,0,res)
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

在二叉树中增加一行

• 方法：递归
  左右子树分别遍历，遍历的时候计算深度，如果当前深度=depth-1，则当前节点下新增两个val的左右节点，当前节点的左右子树分别分给这两个节点

class Solution(object):
    def addOneRow(self, root, val, depth):
        if root == None:
            return root
        def addVal(root,val,depth,cur_dep):
            if root==None:
                return
            if cur_dep == depth-1:
                node1, node2 = TreeNode(val), TreeNode(val)
                node1.left = root.left
                node2.right = root.right
                root.left, root.right = node1, node2
                return 
            addVal(root.left,val,depth,cur_dep+1)
            addVal(root.right,val,depth,cur_dep+1)
        
        if depth==1:
            node = TreeNode(val)
            node.left = root
            root = node
            return root
        addVal(root,val,depth,1)
        
        return root
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

路径和问题

437. Path Sum III （路径和数量）

给定target，求路径和为tagert的路径数，注意路径不一定经过节点或者根节点，但必须是向下走的，值有正有负

class Solution {
   int count = 0;
    public int pathSum(TreeNode root, int targetSum) {
        if(root==null) return 0;
        //遍历不同的父节点
        dfs(root,0,targetSum);
        pathSum(root.left,targetSum);
        pathSum(root.right,targetSum);
        return count;
    }

    public void  dfs(TreeNode root, int cur, int targetSum){
        if(root==null) return ;
        if(cur+root.val== targetSum) count++;
        dfs(root.left,cur+root.val,targetSum);
        dfs(root.right,cur+root.val,targetSum);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

路径总和

• 自己

class Solution(object):
    def pathSum(self, root, sum):
        if root==None:
            return 0
        res = []

        # 从某节点开始,有满足的路径则res中+1
        def rootSum(root,sum,rosum,res):
            if root==None:
                return
            if rosum+root.val == sum:
                res.append(1)
                # 注意：这里不能加return,后面的可能有1 -1的路，和为0抵消,但是是不同路径
            rootSum(root.left,sum,rosum+root.val,res)
            rootSum(root.right,sum,rosum+root.val,res)
        
        # 遍历每个根节点,对每个根节点找路径
        def loop(root,sum,res):
            if root==None:
                return
            rootSum(root,sum,0,res)
            loop(root.left,sum,res)
            loop(root.right,sum,res)

        loop(root,sum,res)
        
        return len(res)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

注意：也可以不用列表存储，直接计算数字，即子函数中对外部数字变量进行更改。例如：

 b = [1]
 def bchange():
   b[0] += 1
 bchange()
 print b[0]
1
2
3
4
5

• 一篇文章解决所有二叉树问题
  https://blog.csdn.net/m0_37870649/article/details/118878204

模板：

1. 自顶而下
   注意：是否要双重递归：看题目要不要求从根节点开始的，还是从任意节点开始

'''
一般路径
'''
res = []
def dfs(root, path):
    if not root:
        return    # 根节点为空直接返回
    if not root.left and not root.right:    # 到叶节点
        res.append(path + [root.val])
        return
    dfs(root.left, path + [root.val])
    dfs(root.right, path + [root.val])
    return

'''
给定和路径
'''
def dfs(root, target, path):
    if not root:
        return
    target -= root.val    # 不同点
    if not root.left and not root.right and target == 0:    # 不同点
        res.append(path + [root.val])
        return
    dfs(root.left, target, path + [root.val])
    dfs(root.right, target, path + [root.val])
  	return
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

注意：不可以下面这样写！！！
原因：path.append和path+[]不一样，path.append遍历到叶子节点后，返回上一节点，再接着下一条路走，path并不会跟着返回，而是再原来的基础上加路。

			res =[]
        def Allpath(root,path):
            if root == None:
                return
            path.append(root.val)
            # 叶子节点停止
            if root.left == None and  root.right == None:
                res.append(path)
                return
            Allpath(root.left,path)
            Allpath(root.right,path)

        Allpath(root,[])
1
2
3
4
5
6
7
8
9
10
11
12
13

双重递归：从任意节点开始看
先调用dfs函数从root开始查找路径，再调用pathsum函数到root左右子树开始查找

count = 0

# 遍历每个节点
def pathSum(root, targetSum):
    if root==None:
        return 0
    dfs1(root, targetSum)            //以root为起始点查找路径
    pathSum(root.left, targetSum)  //左子树递归
    pathSum(root.right, targetSum) //右子树递归
    return count

# 找出符合sum的路径
def dfs(root, sum):

    if (!root):
        return 
    sum -= root.val
    if (sum == 0): //注意不要return,因为不要求到叶节点结束,所以一条路径下面还可能有另一条
        count++  //如果找到了一个路径全局变量就+1
    dfs1(root.left, sum)
    dfs1(root.right, sum)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

2. 非自顶向下

这类题目一般解题思路如下：
设计一个辅助函数maxpath，调用自身求出以一个节点为根节点的左侧最长路径left和右侧最长路径right，那么经过该节点的最长路径就是left+right
接着只需要从根节点开始dfs,不断比较更新全局变量即可

路径总和 II 113. Path Sum II

class Solution(object):
    def pathSum(self, root, targetSum):
        res = []
        def dfs(root,targetSum,path):
            if root==None:
                return
            targetSum -= root.val
            # 到叶子节点且符合sum
            if root.left == None and root.right ==None and targetSum==0:
                res.append(path+[root.val])
                
            dfs(root.left,targetSum,path+[root.val])
            dfs(root.right,targetSum,path+[root.val])

        dfs(root,targetSum,[])
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

从叶节点开始的最小字符串

• 自己：找出所有路径，并且倒叙，找出其中最小的，python可以直接比对[1,2,3]<[1,2,3,4],返回True

class Solution(object):
    def smallestFromLeaf(self, root):

        if root==None:
            return root
        
        res = []

        # 获取所有路径
        def Allpath(root,path):
            if root == None:
                return
            # 叶子节点停止
            if root.left == None and  root.right == None:
                res.append(path+[root.val])
                return 
            Allpath(root.left,path+[root.val])
            Allpath(root.right,path+[root.val])
        # 路径倒排，并找出最小的
        Allpath(root,[])
        for i in range(len(res)):
            res[i].reverse()
        # 获取a到z的字母序
        dic={i-97:chr(i) for i in range(97,123)}
        min_path = res[0]
        for i in range(len(res)):
            if res[i]<min_path:
                min_path = res[i]
        min_path = [dic[x] for x in min_path]
        return ''.join(min_path)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

• 题解方法：回溯

当我们到达一个叶子节点的时候，我们翻转路径的字符串内容来创建一个候选答案。如果候选答案比当前答案要优秀，那么我们更新答案。

class Solution(object):
    def smallestFromLeaf(self, root):
        self.ans = "~"

        def dfs(node, A):
            if node:
                # ord('a')=97,char(98)='b'
                A.append(chr(node.val + ord('a')))
                if not node.left and not node.right:
                    self.ans = min(self.ans, "".join(reversed(A)))
                    
                dfs(node.left, A)
                dfs(node.right, A)
                # 回溯,把岔路删去
                A.pop()

        dfs(root, [])
        return self.ans

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

其他