二叉树遍历

二叉树作为一种常见的数据结构,对于其遍历也是有很多形式,以下记录部分二叉树遍历.

/**
 * Java二叉树表示
 * 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 List<Integer> preorderTraversal(TreeNode root) {
        var ans = new ArrayList<Integer>();
        var stk = new ArrayDeque<TreeNode>();
        if (root == null) return ans;
        stk.addLast(root);
        while (!stk.isEmpty()) {
            var pop = stk.pollLast();
            ans.add(pop.val);
            if (pop.right != null)  //  注意这里的顺序
                stk.addLast(pop.right);
            if (pop.left != null)
                stk.addLast(pop.left);
        }
        return ans;
    }
}

中序遍历(非递归)

中序遍历是比较难的,有两处细节需注意.

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        var ans = new ArrayList<Integer>();
        var stk = new ArrayDeque<TreeNode>();
        while (root != null || !stk.isEmpty()) {  //这里是||
            while (root != null) {
                stk.addLast(root);
                root = root.left;
            }
            root = stk.pollLast();
            ans.add(root.val);
            root = root.right; //  脑子里想一个二叉树来模拟
        }
        return ans;
    }
}

后续遍历(非递归)

//  和前序遍历比较类似,还是比较好想的
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        var ans = new LinkedList<Integer>();
        if (root == null) return ans;
        var stk = new ArrayDeque<TreeNode>();
        stk.addLast(root);
        while (!stk.isEmpty()) {
            var pop = stk.pollLast();
            ans.addFirst(pop.val);
            if (pop.left != null) stk.addLast(pop.left);
            if (pop.right != null) stk.addLast(pop.right);
        }
        return ans;
    }
}

垂直遍历

对于同一层级的同一垂直坐标采取数值比较

class Solution:
    def verticalTraversal(self, root: Optional[TreeNode]) -> List[List[int]]:
        g = [[] for _ in range(30)]
        q = deque([(root, 15)])
        while q:
            sz = len(q)
            temp = []
            for _ in range(sz):
                poll = q.popleft()
                temp.append((poll[1], poll[0].val))
                if poll[0].left: q.append((poll[0].left, poll[1] - 1))
                if poll[0].right: q.append((poll[0].right, poll[1] + 1))
            temp.sort()
            for e in temp: g[e[0]].append(e[1])
                
        ret = []
        for e in g:
            if len(e) != 0:
                ret.append(e)
        return ret

输出[9, 3, 15, 20, 7]

层序遍历(递归)

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root: return []
        g = [[] for _ in range(2000)]

        def dfs(r: 'TreeNode', t: int) -> None:
            g[t].append(r.val)
            if r.left:
                dfs(r.left, t + 1)  # 根据递归的思路，这样写也是符合顺序的
            if r.right:
                dfs(r.right, t + 1)

        dfs(root, 0)
        ret = []
        for e in g:
            if len(e): ret.append(e)
        return ret

前中恢复二叉树

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        n = len(preorder)
        d = {val: idx for idx, val in enumerate(inorder)}
        
        def dfs(pl: int, pr: int, il: int, ir: int) -> Optional[TreeNode]:
            if pl > pr or il > ir: return None
            node = TreeNode(preorder[pl])
            t = d[preorder[pl]]
            node.left = dfs(pl + 1, pl + t - il, il, t - 1)
            node.right = dfs(pl + t - il + 1, pr, t + 1, ir)
            return node

        return dfs(0, n - 1, 0, n - 1)

中后恢复二叉树

class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
        n = len(inorder)
        d = {val: idx for idx, val in enumerate(inorder)}

        def dfs(pl: int, pr: int, il: int, ir: int) -> Optional[TreeNode]:
            if pl > pr or il > ir: return None
            node = TreeNode(postorder[pr])
            t = d[postorder[pr]]
            node.left = dfs(pl, pr - ir + t - 1, il, t - 1)
            node.right = dfs(pr - ir + t, pr - 1, t + 1, ir)
            return node

        return dfs(0, n - 1, 0, n - 1)

前后恢复二叉树

# 前序遍历和后续遍历不能确定一颗二叉树
class Solution:
    def constructFromPrePost(self, pre: List[int], post: List[int]) -> TreeNode:
        n = len(pre)
        d = {val: idx for idx, val in enumerate(post)}

        def dfs(prl: int, prr: int, pol: int, por: int) -> TreeNode:
            if prl > prr: return
            node = TreeNode(pre[prl])
            if prl == prr: return node
            nxt = prl + 1
            t = d[pre[nxt]] - pol
            node.left = dfs(nxt, nxt + t, pol, pol + t)
            node.right = dfs(nxt + t + 1, prr, pol + t + 1, por - 1)
            return node

        return dfs(0, n - 1, 0, n - 1)