树（Tree）

遍历

测试用例

package org.example.test1;

import org.example.datastructure.BinaryTreeNode;
import org.example.util.BinaryTreeTraversalUtil;
import lombok.extern.slf4j.Slf4j;
import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;

import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;

@Slf4j
public class BinaryTreeTraversalTest {
    @Test
    void test() {
        /*
          3
         2  5
        1  4  7
             6
         */
        BinaryTreeNode root = new BinaryTreeNode(3);
        {
            BinaryTreeNode l = new BinaryTreeNode(2);
            BinaryTreeNode r = new BinaryTreeNode(5);
            BinaryTreeNode ll = new BinaryTreeNode(1);
            BinaryTreeNode rl = new BinaryTreeNode(4);
            BinaryTreeNode rr = new BinaryTreeNode(7);
            BinaryTreeNode rrl = new BinaryTreeNode(6);
            root.setLeft(l);
            root.setRight(r);
            l.setLeft(ll);
            r.setLeft(rl);
            r.setRight(rr);
            rr.setLeft(rrl);
        }
        // 前序
        {
            List<Integer> v1 = new ArrayList<>();
            BinaryTreeTraversalUtil.dfsBAC(root, (value) -> {
                v1.add(value);
            });
            log.info("前序: {}", v1);
            // 非递归
            List<Integer> v2 = new ArrayList<>();
            BinaryTreeTraversalUtil.dfsBAC2(root, (value) -> {
                v2.add(value);
            });
            Assertions.assertArrayEquals(v1.toArray(), v2.toArray());
        }
        // 中序
        {
            List<Integer> v1 = new ArrayList<>();
            BinaryTreeTraversalUtil.dfsABC(root, (value) -> {
                v1.add(value);
            });
            log.info("中序: {}", v1);
            // 非递归
            ArrayList<Integer> v2 = new ArrayList<>();
            BinaryTreeTraversalUtil.dfsABC2(root, (value) -> {
                v2.add(value);
            });
            Assertions.assertArrayEquals(v1.toArray(), v2.toArray());
        }
        // 后序
        {
            List<Integer> v1 = new ArrayList<>();
            BinaryTreeTraversalUtil.dfsACB(root, (value) -> {
                v1.add(value);
            });
            log.info("后序: {}", v1);
            // 非递归
            ArrayList<Integer> v2 = new ArrayList<>();
            BinaryTreeTraversalUtil.dfsACB2(root, (value) -> {
                v2.add(value);
            });
            Assertions.assertArrayEquals(v1.toArray(), v2.toArray());
        }
        // 层序遍历
        {
            List<List<Integer>> tree = new ArrayList<>();
            BinaryTreeTraversalUtil.bfs(root, (level, val) -> {
                if (tree.size() > level-1) {
                    tree.get(level-1).add(val);
                } else {
                    List<Integer> flow = new ArrayList<>();
                    flow.add(val);
                    tree.add(flow);
                }
            });
            // show
            for (int i = 0; i < tree.size(); i++) {
                List<String> flow = tree.get(i).stream()
                        .map(v -> v==null ? "#" : String.valueOf(v))
                        .collect(Collectors.toList());
                log.info("{}: {}", i, flow);
            }
        }
    }
}

实现

package org.example.util;

import org.example.datastructure.BinaryTreeNode;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
import java.util.function.BiConsumer;
import java.util.function.Consumer;

public class BinaryTreeTraversalUtil {
    /**
     * 前序
     */
    public static void dfsBAC(BinaryTreeNode root, Consumer<Integer> func) {
        if (root == null) {
            return;
        }
        func.accept(root.getVal());
        dfsBAC(root.getLeft(), func);
        dfsBAC(root.getRight(), func);
    }

    /**
     * 前序
     * ❗非递归
     */
    public static void dfsBAC2(BinaryTreeNode root, Consumer<Integer> func) {
        BinaryTreeNode cur = root;
        Stack<BinaryTreeNode> stack = new Stack<>();
        while(cur!=null || !stack.isEmpty()) {
            if (cur != null) {
                func.accept(cur.getVal());
                stack.push(cur.getRight());
                stack.push(cur.getLeft());
            }
            cur = stack.pop();
        }
    }

    /**
     * 中序
     */
    public static void dfsABC(BinaryTreeNode root, Consumer<Integer> func) {
        if (root == null) {
            return;
        }
        dfsABC(root.getLeft(), func);
        func.accept(root.getVal());
        dfsABC(root.getRight(), func);
    }

    /**
     * 中序
     * ❗非递归
     */
    public static void dfsABC2(BinaryTreeNode root, Consumer<Integer> func) {
        BinaryTreeNode cur = root;
        Stack<BinaryTreeNode> stack = new Stack<>();
        while(cur!=null || !stack.isEmpty()) {
            if (cur != null) {
                stack.push(cur);
                cur = cur.getLeft();
                continue;
            }
            cur = stack.pop();
            func.accept(cur.getVal());
            cur = cur.getRight();
        }
    }

    /**
     * 后序
     */
    public static void dfsACB(BinaryTreeNode root, Consumer<Integer> func) {
        if (root == null) {
            return;
        }
        dfsACB(root.getLeft(), func);
        dfsACB(root.getRight(), func);
        func.accept(root.getVal());
    }

    /**
     * 后序：左右中
     * ❗非递归
     */
    public static void dfsACB2(BinaryTreeNode root, Consumer<Integer> func) {
        BinaryTreeNode cur = root;
        Stack<BinaryTreeNode> stack = new Stack<>();
        Stack<BinaryTreeNode> callback = new Stack<>();
        while(cur!=null || !stack.isEmpty()) {
            if (cur != null) {
                callback.push(cur); // 💡用于反转： 中右左 -> 左右中（后序）
                stack.push(cur.getLeft());
                stack.push(cur.getRight());
            }
            cur = stack.pop();
        }
        // callback
        while (!callback.isEmpty()) {
            BinaryTreeNode pop = callback.pop();
            func.accept(pop.getVal());
        }
    }

    public static void bfs(BinaryTreeNode root, BiConsumer<Integer, Integer> func) {
        Queue<BinaryTreeNode> queue = new LinkedList<>();
        int size = 1; // ❗记录当前层数量
        int level = 1;
        queue.add(root);
        while (!queue.isEmpty()) {
            while(size > 0) {
                size--;
                BinaryTreeNode cur = queue.poll();
                func.accept(level, cur == null ? null : cur.getVal());
                if (cur == null) {
                    continue;
                }
                queue.add(cur.getLeft());
                queue.add(cur.getRight());
            }
            size = queue.size();
            level++;
        }
    }

    /**
     * 1,2,3,4,#,5,6
     * 1,2
     */
//    public BinaryTreeNode fromString(String str) {
//        Iterable<String> split = Splitter.on(',').trimResults().omitEmptyStrings().split(str);
//    }
}

相关例题：DFS

• LeetCode：222.完全二叉树节点的数量 （有特解）
• LeetCode：110.平衡二叉树
• LeetCode：257. 二叉树的所有路径
• LeetCode：112. 路径总和
• LeetCode：106.从中序与后序遍历序列构造二叉树 （逆向生成树，KMP 算法）

相关例题：BFS

• LeetCode：513. 找树左下角的值 （层序、先序均可）

提示

在完全遍历的情况下，解题方式中，DFS 效率优于 BFS （猜测：不用创建内存的缘故把）

深度优先遍历（DFS）

概要

• 前序：中左右
• 中序：左中右
• 后序：左右中

递归法

/**
 * 前序：中左右
 */
void traversal(cur, vec) {
  if (cur == null) {
    return;
  }
  vec.push(cur->val); // 中
  traversal(cur->left, vec); // 左
  traversal(cur->right, vec); // 右
}

非递归法

todo pseudo code

// 前序：中左右
BinaryTreeNode cur = root;
Stack<BinaryTreeNode> stack = new Stack<>();
while(cur!=null || !stack.isEmpty()) {
    if (cur != null) {
        func.accept(cur.getVal());
        stack.push(cur.getRight());
        stack.push(cur.getLeft());
    }
    cur = stack.pop();
}

层序遍历（广度优先，BFS）【重要】

public static void bfs(BinaryTreeNode root, BiConsumer<Integer, Integer> func) {
    Queue<BinaryTreeNode> queue = new LinkedList<>();
    int size = 1; // ❗记录当前层数量
    int level = 1;
    queue.add(root);
    while (!queue.isEmpty()) {
        while(size > 0) {
            size--;
            BinaryTreeNode cur = queue.poll();
            func.accept(level, cur == null ? null : cur.getVal());
            if (cur == null) {
                continue;
            }
            queue.add(cur.getLeft());
            queue.add(cur.getRight());
        }
        size = queue.size();
        level++;
    }
}

问题：深度

相关例题：

• LeetCode：104.二叉树的最大深度
• LeetCode：111.二叉树的最小深度

easy

问题：反转

相关例题：

• LeetCode：226.翻转二叉树

/**
 * 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 invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        TreeNode l = invertTree(root.left);
        TreeNode r = invertTree(root.right);
        root.left = r;
        root.right = l;
        return root;
    }
}

问题：判断是否对称

相关问题：

• LeetCode：101. 对称二叉树

双指针

/**
 * 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 boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        return xx(root.left, root.right);
    }
    boolean xx(TreeNode left, TreeNode right) {
        if (left == null && right == null) return true;
        if (left == null || right == null) return false;
        if (left.val != right.val) return false;
        return xx(left.left, right.right) && xx(left.right, right.left);
    }
}