二叉树

算法
字数统计: 4.4k   |   阅读时长≈ 20 分钟

二叉树

二叉树节点定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
 * 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;
 *     }
 * }
 */

二叉树的前序遍历

递归法

迭代法

方法一：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public List<Integer> preorderTraversal(TreeNode root) {
    // iteratively
    List<Integer> result = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    while (root != null) {
        result.add(root.val);
        if (root.right != null) {
            stack.push(root.right);
        }
        root = root.left;
        if (root == null && !stack.empty()) {
            root = stack.pop();
        }
    }
    return result;
}

方法二：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//preorder
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if(root == null) return list;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while(!stack.isEmpty()) {
            TreeNode current = stack.pop();
            list.add(current.val);
            if(current.right!=null) {
               stack.push(current.right);
            }
            if(current.left!=null) {
              stack.push(current.left);
            }
        }
        return list;
    }

二叉树的中序遍历

leetcode 94. Binary Tree Inorder Traversal

递归法

迭代法

方法一：依然是将所有点先压入栈中，先将根节点与左子树压入，然后弹出时再根据情况判断有否遍历右子树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//inorder
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res=new ArrayList<>();
        if (root==null) return res;

        Stack<TreeNode> stack=new Stack<>();
        TreeNode curr=root;

        while(curr!=null || !stack.isEmpty()){
            while (curr!=null){
                stack.push(curr);
                curr=curr.left;
            }
            curr=stack.pop();
            res.add(curr.val);
            curr=curr.right;
        }
        return res;
    }

方法二：与前序遍历直接将根节点添加到result中不同，因为中序遍历时先遍历左子树，再访问root节点，所以root节点需要先压入栈中，然后继续遍历左子树，然后弹出时再添加root节点的值，并考虑是否遍历右子树。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    Stack<TreeNode> nodes = new Stack<>();
    while(root != null) {
        nodes.push(root);
        root = root.left;
        while(root == null && !nodes.isEmpty()) {
            root = nodes.pop();
            result.add(root.val);
            root = root.right;
        }

    }
    return result;
}

莫里斯 Morris 遍历法

总体思路： 将二叉树变为单向链表，不借助Stack或队列等外部数据结构，充分利用指针来操作。

二叉树的后序遍历

迭代法

思路：
// 因为后续遍历逆序结果等于前序遍历（先右子树）的结果
// 所以将前序遍历（先右子树）的结果通过栈逆序输出即可

这里有两种做法，

方法一，只选择一侧压入，其他的进行判断处理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 前序遍历时，选择右侧压入，
// 后序遍历时，因为是前序遍历（先右子树）的逆序，所以当做前序遍历右侧优先的方式遍历，选择左侧压入。
public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    Stack<TreeNode> nodes = new Stack<>();
    while(root != null) {
        // 这个方法表示，将值插入0索引位置，然后后序再插入值时，
        // 如果0索引点有值，则将所有值向右移动（索引加一），然后将值插入0索引位置。
        // 效果与正常add后，反转一样。Collections.reverse();
        result.add(0, root.val);
        if (root.left != null) {
            nodes.push(root.left);
        }
        root = root.right;
        if (root == null && !nodes.isEmpty()) {
            root = nodes.pop();
        }
    }
    return result;
}

方法二，所有节点都压入，只是根据先遍历的顺序，选择先压入左右哪边的节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 将所有遍历的点都压入栈中，然后依次弹出，
// 压入的顺序的选择与方法一相同，
// 前序遍历时先压入右侧，在压入左侧，因为要优先遍历左侧，
// 后序遍历因为是前序遍历（先右侧）的结果逆序，所以要先遍历右侧，即先压入左侧。
public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    Stack<TreeNode> nodes = new Stack<>();
    if (root == null) return result; 
    nodes.push(root);
    while(!nodes.isEmpty()) {
        root = nodes.pop();
        // 这里同样利用该方法达到，反转list的效果，Collections.reverse();
        result.add(0, root.val);
        if (root.left != null) {
            nodes.push(root.left);
        }
        if (root.right != null) {
            nodes.push(root.right);
        }
    }
    return result;
}

方法二+1：这个方法比方法二更好一些，主要是使用的数据结构更好一些

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 这个方法贴下来的目的是，它使用了LinkedList,和 addFirst()方法，
// addFirst()方法可以达到从后向前添加元素的效果，同时该方法的时间复杂度为 O(1)
public List<Integer> postorderTraversal(TreeNode root) {
	LinkedList<Integer> ans = new LinkedList<>();
	Stack<TreeNode> stack = new Stack<>();
	if (root == null) return ans;
	
	stack.push(root);
	while (!stack.isEmpty()) {
		TreeNode cur = stack.pop();
		ans.addFirst(cur.val);
		if (cur.left != null) {
			stack.push(cur.left);
		}
		if (cur.right != null) {
			stack.push(cur.right);
		} 
	}
	return ans;
}

这里就涉及到ArrayList 与 LinkedList 的区别了

ArrayList.add(index, element) 方法，底层是使用了Array的相关操作，数组对于迁移插入数据，时间复杂度为O(n)，
LinkedList.addFirst() 方法，实现时使用了双向链表节点，插入的时间复杂度为O(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
48
49
50
51
52
53
54

// Pre Order Traverse
public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode p = root;
    while(!stack.isEmpty() || p != null) {
        if(p != null) {
            stack.push(p);
            result.add(p.val);  // Add before going to children
            p = p.left;
        } else {
            TreeNode node = stack.pop();
            p = node.right;   
        }
    }
    return result;
}

// In Order Traverse
public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode p = root;
    while(!stack.isEmpty() || p != null) {
        if(p != null) {
            stack.push(p);
            p = p.left;
        } else {
            TreeNode node = stack.pop();
            result.add(node.val);  // Add after all left children
            p = node.right;   
        }
    }
    return result;
}

// Post Order Traverse
public List<Integer> postorderTraversal(TreeNode root) {
    LinkedList<Integer> result = new LinkedList<>();
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode p = root;
    while(!stack.isEmpty() || p != null) {
        if(p != null) {
            stack.push(p);
            result.addFirst(p.val);  // Reverse the process of preorder
            p = p.right;             // Reverse the process of preorder
        } else {
            TreeNode node = stack.pop();
            p = node.left;           // Reverse the process of preorder
        }
    }
    return result;
}

前序，中序，后序遍历的Morris解法

如果使用的是非递归方式，我们要么需要一个栈，要么需要一个队列来维护节点之间的关系。如果使用Morris遍历就不需要了，

因为一般情况下，二叉树的叶子节点是没有子节点的，也就是说他们是指向空，Morris的实现原理其实就是把叶子节点的指针给利用了起来。

Morris的中序遍历，可以把它看做是把二叉树拉直变成了链表

关于Morrios更详细的内容，请查看Threaded binary tree 和 Explaination of Morris Method

1
参考代码...

层序遍历 （BFS 广度优先）

通常，我们使用一个叫做queue队列的数据结构来帮助我们做广度优先搜索。

按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）

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
public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    Queue<TreeNode> queue = new LinkedList<>();
    if (root == null) return result;
    // 先放入根节点
    queue.offer(root);
    // 队列不为空
    while(!queue.isEmpty()) {
        int size = queue.size();
        List<Integer> level = new ArrayList<>();
        // 一次循环一层，所以必然会有一个内部循环
        // 按层放入节点到队列，然后将队列中的一层节点拿出来一次循环
        // 将下一层节点加入到队列中
        for(int i = 0; i< size;i++) {
            TreeNode node = queue.poll();
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
            level.add(node.val);
        }
        result.add(level);
    }
    return result;
    
}

树的最大深度 104

练习题集合

1
2
3
4
5
6
7
8
9
10
11
is - start index for inorder array
ie - end index for inorder array

ps - start index for postorder array
pe - end index for postorder array

Remember :
InOrder is (left subtree) node (right subtree)
PostOrder is (left subtree)(right subtree) (node)
From post order array we get the root which will be at index pe
while from in order we can get the number of children in the left subtree ie. ri-is
  1. Construct Binary Tree from Preorder and Inorder Traversal

A tree has a recursive structure because it has subtrees which are trees themselves.
一棵树具有递归结构，因为它有子树，而子树本身也是树。

Populating Next Right Pointers in Each Node (116. 填充每个节点的下一个右侧节点指针)

  • 典型的BFS策略
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

//BFS的迭代解法
// 总体流程是，外层while是，从上到下的遍历，内存while是，对当前层所有节点的遍历。
class Solution {
    public Node connect(Node root) {
        if (root == null) return null;
        Node pre = root;
        // 直接判断下一层是否有值，有值则继续，没值则退出；
        while(pre.left != null) {
            // 遍历当前层的所有节点。访问当前层节点的同时，连接下一层的节点。
            Node cur = pre;
            while(cur != null) {
                cur.left.next = cur.right;
                if (cur.next != null) cur.right.next = cur.next.left;
                cur = cur.next;
            }
            // 当前层所有节点遍历完，就遍历下一层。
            pre = pre.left;
        }
        return root;
    }
}


Populating Next Right Pointers in Each Node II（117. 填充每个节点的下一个右侧节点指针 II）

  • 这个版本是普通的二叉树（节点可能，或者没有子节点，或者没有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
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
class Solution {
    // easy to understand solution1
    // two while loops, but the meaning is clearer
    public Node connect(Node root) {
        if (root == null) return null;
        Node levelStart = root; // 每层的开始节点
        Node dummyNode = new Node(-1);
        Node p = dummyNode;
        // if the  of the traverse layer is not null, then traverse that layer...
        while(levelStart != null) {
            Node cur = levelStart;
            // 开始遍历每一层的每个节点
            while(cur != null) {
                if (cur.left != null) {
                    p.next = cur.left;
                    p = p.next;
                }
                if (cur.right != null) {
                    p.next = cur.right;
                    p = p.next;
                }
                // 遍历下一个节点
                cur = cur.next;
            }
            // 通过复制辅助节点的指针，进入下一层
            levelStart = dummyNode.next;
            // 将辅助节点的next指针断掉，方便下一层使用，这样就只需要创建一个辅助节点了
            dummyNode.next = null;
            // p指向辅助节点便于后面操作next指针
            p = dummyNode;
        }
        return root;
    }
}

// 另外一个版本，性能是一样的，思路也清晰
class Solution {
    public Node connect(Node root) {
        if (root == null) return null;
        Node cur = root;
        Node dummyNode = new Node(-1);
        Node p = dummyNode;
        while(cur != null) {
            if (cur.left != null) {
                p.next = cur.left;
                p = p.next;
            }
            if (cur.right != null) {
                p.next = cur.right;
                p = p.next;
            }
            if (cur.next != null) {
                cur = cur.next;
            } else {
                cur = dummyNode.next;
                dummyNode.next = null;
                p = dummyNode;
            }
        }
        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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
    public Node connect(Node root) {
        if (root == null) return null;
        if (root.left != null) { // 更新left.next
            if (root.right != null) { // 判断是否存在right，如果不存在就找root.next
                root.left.next = root.right;
            } else {
                root.left.next = findNext(root);
            }
        }
        // 更新right.next，直接找root.next
        if (root.right != null) root.right.next = findNext(root);
        
        // 这里要重点说一下，为什么要先更新right subtree，
        // 因为如果先更新left subtree，因为每次递归只能更新半棵树（每一层右半边会有节点无法被next连接上），
        // 这样会导致往下递归时，会导致下面的节点的next无法连接。
        // 所以先递归right subtree，这样先连接右半边，再连接左半边，可以保证递归完成后每一层所有node都有next连接上。
        // 下面有例子
        connect(root.right);
        connect(root.left);
        return root;
    }
    
    /**
    * 寻找root同层的其他Node
    */
    private Node findNext(Node root) {
        while(root.next != null) {
            root = root.next;
            if (root.left != null) return root.left;
            if (root.right != null) return root.right;
        }
        return null;
    }
}


举例佐证先更新right subtree
[1,2,3,4,5,6,7,8,null,null,9]
在这个例子中，如果先更新left subtree，那么由于递归过程总，6与7没有通过next来接上，导致递归到8时，8无法与9连接上。

最近公共祖先

递归方法的思路和题解

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
    /**
     * 算法思路：
     * 1. 从root节点开始遍历整棵树；
     * 2. 如果发现p,q任何一个节点，就返回；利用root == q || root == p，说明找到了节点
     * 3. 如果当前节点不符合要求，分别查找左右子树；
     * 4. 如果左右子树返回值都不为null，说明p，q分别在左右子树中，则该节点为祖先节点；
     * 5. 如果左子树或者右子树有一个返回了指定节点，另一个为null，说明p,q有一个在其分支中，
     * 特别的，如果返回到顶层后，只有一侧分支有返回值，说明p,q两个节点都在返回值所在的子树中。该返回值就是p,q的祖先。
     */
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) return root;
        // search left subtree
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        // search right subtree
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        // 
        if (left != null && right != null) return root;
        return left != null ? left : right;
    }
}

举例：
给定二叉树：[1,2,3,4,5,6,7],输入p=2,q=5,
1.在这个二叉树中，从根节点1出发，遍历到1的左子树2时，找到节点p，然后返回，
2.接着遍历1的右子树3，遍历完，右子树返回为null，因为没有找到q，
3.最终返回2。
说明：在这个二叉树中，2，和5都在2所在的左子树中，当遍历完左右子树时，右子树没有符合条件的节点，左子树2符合其中一点，说明另一点一定在2所在的左子树分支中，此时2就是2和5的最近公共祖先。（节点可以是其本身的祖先的。）
    

如果是p,q分别在某个节点的左右子树中，那么对于"该节点"来说返回情况是left！=null&&right != null，对于整个树来说，当递归栈返回到顶层后的表现为lef子树或者right子树其中一个的返回值为"该节点"，另一边为null。

官方解法说明中的思路提挺好的，后面做题时，可以尝试画

1
2
3
4
5
6
7
8
9
10
11
12
以下是递归过程中节点的序列：

1 --> 2 --> 4 --> 8
BACKTRACK 8 --> 4
4 --> 9 (ONE NODE FOUND, return True)
BACKTRACK 9 --> 4 --> 2
2 --> 5 --> 10
BACKTRACK 10 --> 5
5 --> 11 (ANOTHER NODE FOUND, return True)
BACKTRACK 11 --> 5 --> 2

2 is the node where we have left = True and right = True and hence it is the lowest common ancestor.

关于递归优化的问题

如果我们已经在左子树中找到祖先节点，如何避免对剩下右子树不必要的递归检查工作？

首先我们在优化的时候要意识到，

  1. the purpose is to stop further unnecessary recursive call. You can’t really terminate the function early without using exception.

目的是阻止进一步不必要的递归调用。如果不使用异常，您无法真正提前终止该函数。

  1. In recursion no matter what you return the called stack has to unwind back. So this is not really termination.

在递归中，无论您返回什么，已经调用的栈都必须展开。所以这并不是真正的终止。

  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
// 递归版本，去掉flag部分就是常规版本
class Solution {
    // 这里添加两个flag用于提前判断
    boolean p_found = false, q_found = false;
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null) return null;
        if(root.val == p.val){
            p_found = true;
            return root;
        }
        if(root.val == q.val){
            q_found = true;
            return root;
        }
        // 上面内容，如果在常规版本中，可以合并一起写
        // if (root == null || root == q || root == p) return root;
        
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        
        // 两个flag主要用于判断当左子树找到祖先，不进行后面不必要的递归检查。
        if(p_found && q_found)
            return left;
        
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        
        if(left != null && right != null) return root;
        
        return left == null? right : left;
    }
}

迭代思路和解法

遍历p,q的时候，将其父节点都保存下来，然后分别对比两个节点的祖先节点，找到公共祖先。

问题，找最近公共祖先，使用什么数据结构存储父节点和祖先节点？

  1. Map来存储每个点和其父节点；
  2. 找到p,q点时，利用从p,或q直接父节点一层层向上找的方式，先找到的一定是最近公共祖先。
  3. 在循环过程中使用Deque或者Queue都行，都可以实现层序遍历的功能（这题用DFS或者BFS迭代都可以，BFS时，可以按层遍历，倘若要寻找的点p,q在同一层，那么下面层就可以不遍历了。DFS时，如果p,q在同一侧分支，则其他分支不用遍历。）
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 {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        Queue<TreeNode> queue = new LinkedList<>();
        HashMap<TreeNode, TreeNode> parents = new HashMap<>();
        queue.offer(root);
        parents.put(root, null);
        while(!parents.containsKey(p) || !parents.containsKey(q)){
            TreeNode node = queue.poll();
            if (node.left != null) {
                parents.put(node.left, node);
                queue.offer(node.left);
            }
            if (node.right != null) {
                parents.put(node.right, node);
                queue.offer(node.right);
            }
        }
        
        // 处理p的所有祖先节点
        Set<TreeNode> ancestors = new HashSet<>();
        while(p != null) {
            ancestors.add(p);
            p = parents.get(p);
        }
        
        // 通过一层层向上查找q的直接父节点，然后与p的祖先节点进行比较，找到最近公共祖先LCA
        while(!ancestors.contains(q)) {
            q = parents.get(q);
        }
        return q;
    }
}

https://leetcode.com/explore/learn/card/data-structure-tree/133/conclusion/995/discuss/74264/Short-and-straight-forward-BFS-Java-code-with-a-queue

  • 版权声明： 本博客所有文章除特别声明外，著作权归作者所有。转载请注明出处！
  • Copyrights © 2022-2023 ligongzhao
  • 访问人数: | 浏览次数:

请我喝杯咖啡吧~

支付宝
微信