二叉树相关算法

144. 二叉树前序遍历
94. 二叉树的中序遍历
145. 二叉树的后序遍历
102. 二叉树的层序遍历
100. 相同的树
101. 对称二叉树
104. 二叉树的最大深度
110. 平衡二叉树
226. 翻转二叉树
543.二叉树的直径
617. 合并二叉树
897. 递增顺序搜索树
剑指 Offer 32 - II. 从上到下打印二叉树 II

一、二叉树的遍历

二叉树的遍历分为深度遍历和广度遍历。深度优先遍历有前序、中序、后续三种遍历方法；广度优先遍历即平时所说的层次遍历。因为树的定义本身是递归定义，因此采用递归方法实现树的三种遍历不仅容易理解而且代码更简洁。而对于广度遍历来说需要其他数据结构的支撑才能实现遍历。

1. 二叉树的数据结构

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;
    }
}

2. 二叉树遍历思想

前序遍历：根节点-->左子树-->右子树
中序遍历：左子树-->跟节点-->右子树
后续遍历：左子树-->右子树-->根节点
层次遍历：按层遍历即可

以上图为例，前序、中序、后序及层序遍历的结果为：

前序遍历：1 2 4 5 7 8 3 6
中序遍历：4 2 7 5 8 1 3 6
后序遍历：4 7 8 5 2 6 3 1
层序遍历：1 2 3 4 5 6 7 8

二、代码实现

1.深度优先遍历

144. 前序遍历

递归法实现

前序遍历的递归实现非常简单，先获取root节点的值并存储到集合，然后分别递归遍历左子树和右子树即可。

 List<Integer> list = new ArrayList<>();
public List<Integer> preorderTraversal(TreeNode root){
		if(root == null){
      return list;
    }
  list.add(root.val);
  preorderTraversal(root.left);
  preorderTraversal(root.right);
  return list;
}

迭代法实现

前序遍历的迭代实现需要借助栈的数据结构。首先，将根节点push到栈中，通过while循环判断如果栈中为null，则终止循环。否则，则将根节点pop出栈，取出值，并分别判断右子、左子树是否为null，如果不为null则分别加入到栈中。直至遍历完整棵树为止。

public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) {
        return result;
    }
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        result.add(node.val);
        if (node.right != null)
            stack.push(node.right);
        if (node.left != null)
            stack.push(node.left);
    }
    return result;
}

94. 二叉树的中序遍历

递归法实现

定义inorderTraversal(root) 表示当前遍历到 root 节点的答案，按照中序遍历定义，只要递归调用 inorderTraversal(root.left)，然后将root节点的值加入集合，再递归调用inorderTraversal(root.right)来遍历 root 节点的右子树即可。递归终止条件为碰到空节点。

时间复杂度： O(n) 。其中 n 为二叉树节点个数。二叉树遍历每个节点会被访问一次，且只会被访问一次。

空间复杂度： O(n) 。空间复杂度取决于递归的栈深度，而栈深度在二叉树为一条链的情况下回达到O(n)的级别。

List<Integer> result = new ArrayList<>();
public List<Integer> inorderTraversal(TreeNode root) {
		if(root == null){
      return result;
    }
  inorderTraversal(root.left);
  result.add(root.val);
  inorderTraversal(root.right);
  return result;
}

迭代法实现

和前序遍历的迭代实现类似，区别是考察到当期节点时，并不直接输出该节点的值，而是将其入栈，然后迭代遍历其左节点，并将这些节点都加入栈。直至遍历到左节点为空，则从栈pop出一个节点，并读取该节点的值，然后获取其右节点，将右节点再次进行上述的迭代遍历，直至整棵树遍历完成。

public List<Integer> inorderTraversal(TreeNode root) {
	Stack<TreeNode> stack = new Stack<>();
  List<Integer> result = new ArrayList<>();
  TreeNode treeNode = root;
  while(treeNode != null|| !stack.isEmpty()){
    if(treeNode != null){
      stack.push(treeNode);
      treeNode = treeNode.left;
    } else {
      	TreeNode node = stack.pop();
      	result.add(node.val);
        treeNode = node.right;
    }
  }
  return result;
}

中序遍历模板

while(node!= null || !stack.isEmpty){
	if(node != null){ // 这一步主要是为了遍历到树的左叶子节点
    // 1.node 入栈
    // 2.让node等于node的左节点
  } else {
    // 此时树的最左节点全部被加入栈中
    // 1.pop出栈得到最左叶子节点并打印叶子节点的值
    // 2.获取这个节点的右节点
  }
}

145. 二叉树的后序遍历

递归法实现

List<Integer> list = new ArrayList<>();
public List<Integer> postorderTraversal(TreeNode root) {
  if(root == null) {
    return list;
  }
  postorderTraversal(root.left);
  postorderTraversal(root.right);
  list.add(root.val);
  return list;
}

迭代法实现

    public List<Integer> postorderTraversal2(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if(root == null){
            return result;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode node = root,right = null;

        while(node != null || !stack.isEmpty()){
            if(node != null){
                stack.push(node);
                node = node.left;
            } else {
                node = stack.peek();
                if(node.right != null && node.right != right){
                    node = node.right;
                } else {
                    result.add(node.val);
                    right = node;
                    stack.pop();
                    node = null;
                }
            }
        }
        return result;
    }

public List<Integer> postorderTraversal(TreeNode root) {
  List<Integer> result = new ArrayList<>();
  if(root == null){
    return result;
  }
  Stack<TreeNode> stack = new Stack<>();
  TreeNode node = root,right = null;
 
	while(node != null || !stack.isEmpty()){
    if(node != null){
      stack.push(node);
      node = node.left;
    } else {
      node = stack.peek();
      if(node.right != null && node.right != right){
        node = node.right;
      } else {
        result.add(node.val);
        right = node;
        stack.pop();
        node = null;
      }
    }
  }
  return result;
}

2. 广度优先遍历

102. 二叉树的层序遍历

可以使用队列的结构实现二叉树的层序遍历。将每一层的节点放入队列中，得到这一层的节点个数，然后通过for循环遍历这一层的所有节点。通过queue的poll方法将队列的头结点取出，并读取节点的值，然后查看其是否有左右子节点。如果有则通过offer分别将左节点与右节点加入队列。for循环遍历完之后，队列中剩下的就只有下一层的元素了。通过while循环继续遍历下一层即可。

    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null)
            return result;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            ArrayList<Integer> levelList = new ArrayList<>();
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                levelList.add(node.val);
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            result.add(levelList);
        }
        return result;
    }

三、常见二叉树相关题目

100. 相同的树

public class LeetCode100 {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        } else if (p == null || q == null || p.val != q.val) {
            return false;
        } else {
            return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
        }
    }
}

101. 对称二叉树

public class LeetCode101 {
    public boolean isSymmetric(TreeNode root) {
        return checkSubTree(root, root);
    }

    private boolean checkSubTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        }
        if (p == null || q == null) {
            return false;
        }
        return p.val == q.val && checkSubTree(p.right, q.left) && checkSubTree(p.left, q.right);
    }
}

104. 二叉树的最大深度

解法一：深度优先递归查找

public int maxDepth(TreeNode root) {
    if (root == null) {
        return 0;
    } else {
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }
}

解法二：广度优先

public int maxDepth2(TreeNode root) {
    if (root == null) {
        return 0;
    }
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    int level = 0;
    while (!queue.isEmpty()) {
        int n = queue.size();
        for (int i = 0; i < n; i++) {
            TreeNode node = queue.poll();
            if (node != null) {
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
        }
        level++;
    }
    return level;
}

110. 平衡二叉树

public boolean isBalanced(TreeNode root) {
    if (root == null || (root.right == null && root.left == null)) {
        return true;
    }
    return Math.abs(getTreeDepth(root.left) - getTreeDepth(root.right)) <= 1 && isBalanced(root.right) && isBalanced(root.left);
}

private int getTreeDepth(TreeNode node) {
    if (node == null) {
        return 0;
    }
    return Math.max(getTreeDepth(node.right), getTreeDepth(node.left)) + 1;
}

226. 翻转二叉树

public TreeNode invertTree(TreeNode root) {
    if (root == null) {
        return null;
    }
    TreeNode leftNode = invertTree(root.left);
    TreeNode rightNode = invertTree(root.right);
    root.left = rightNode;
    root.right = leftNode;
    return root;
}

543. 二叉树的直径

class Solution {
    int res;

    public int diameterOfBinaryTree(TreeNode root) {
        getTreeDepth(root);
        return res;
    }

    private int getTreeDepth(TreeNode root) {
        if (root == null) return 0;
        int leftDepth = getTreeDepth(root.left);
        int rightDepth = getTreeDepth(root.right);
        res = Math.max(res, rightDepth + leftDepth);
        return Math.max(leftDepth, rightDepth) + 1;
    }
}

617. 合并二叉树

public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
    if (root1 == null) {
        return root2;
    }
    if (root2 == null) {
        return root1;
    }
    root1.val = root1.val + root2.val;
    root1.left = mergeTrees(root1.left, root2.left);
    root1.right = mergeTrees(root1.right, root2.right);
    return root1;
}

897. 递增顺序搜索树

Queue<TreeNode> queue = new LinkedList<>();

public TreeNode increasingBST(TreeNode root) {
    doTraversal(root);
    TreeNode node = queue.poll();
    TreeNode head = node;
    while (!queue.isEmpty()) {
        node.right = queue.poll();
        node.left = null;
        node = node.right;
    }
    node.left = null;
    node.right = null;
    return head;
}


public void doTraversal(TreeNode root) {
    if (root == null) {
        return;
    }
    doTraversal(root.left);
    queue.offer(root);
    doTraversal(root.right);
}

剑指 Offer 32 - II. 从上到下打印二叉树 II

public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> resultList = new ArrayList<>();
    if (root == null) {
        return resultList;
    }
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        int size = queue.size();
        ArrayList<Integer> arrayList = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            if (node != null) {
                if (node.left != null)
                    queue.offer(node.left);
                if (node.right != null) {
                    queue.offer(node.right);
                }
                arrayList.add(node.val);
            }
        }
        resultList.add(arrayList);
    }
    return resultList;
}

开源库推荐

最好用的轮播图库：BannerViewPager

ViewPager指示器：ViewPagerIndicator

Contact

欢迎加群交流:

QQ群	入群加微信

二叉树相关算法

目录

一、二叉树的遍历

1. 二叉树的数据结构

2. 二叉树遍历思想

二、代码实现

1.深度优先遍历

2. 广度优先遍历

三、常见二叉树相关题目

推荐关注公众号，建立自己的Android知识体系。

开源库推荐

最好用的轮播图库：BannerViewPager

ViewPager指示器：ViewPagerIndicator

Contact

Java基础

面向对象与Java基础知识

Java集合框架

JVM

多线程与并发

设计模式

Kotlin

Android

Android基础知识

Android消息机制

Framework

View事件分发机制

Android屏幕刷新机制

View的绘制流程

Activity启动

性能优化

Jetpack&系统View

第三方框架实现原理

计算机网络

算法

其它

Clone this wiki locally