Dabc13c1a7c4c4e7b06225898ac0b2ed
几道和「二叉树」有关的算法面试题

1. 二叉树的前序遍历

题目来源于 LeetCode 第 144 号问题:二叉树的前序遍历。

题目描述

给定一个二叉树,返回它的 前序 遍历。

题目解析

栈(Stack)的思路来处理问题。

前序遍历的顺序为根-左-右,具体算法为:

  • 把根节点push到栈中
  • 循环检测栈是否为空,若不空,则取出栈顶元素,保存其值
  • 看其右子节点是否存在,若存在则push到栈中
  • 看其左子节点,若存在,则push到栈中。

动画描述

二叉树的前序遍历

二叉树的前序遍历

代码实现

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        List<Integer> list = new LinkedList<>();
        if(root == null){
            return list;
        }
        //第一步是将根节点压入栈中
        stack.push(root);
        //当栈不为空时,出栈的元素插入list尾部。
        while(!stack.isEmpty()){
            root = stack.pop();
            list.add(root.val);
            if(root.right != null) stack.push(root.right);
            if(root.left != null) stack.push(root.left);
        }
        return list;
    }
}

2. 二叉树的中序遍历

题目来源于 LeetCode 第 94 号问题:二叉树的中序遍历。

题目描述

给定一个二叉树,返回它的 中序 遍历。

题目解析

栈(Stack)的思路来处理问题。

中序遍历的顺序为左-根-右,具体算法为:

  • 从根节点开始,先将根节点压入栈
  • 然后再将其所有左子结点压入栈,取出栈顶节点,保存节点值
  • 再将当前指针移到其右子节点上,若存在右子节点,则在下次循环时又可将其所有左子结点压入栈中

动画描述

二叉树的中序遍历

二叉树的中序遍历

代码实现

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

3. 二叉树的后序遍历

题目来源于 LeetCode 第 145 号问题:二叉树的后序遍历。

题目描述

给定一个二叉树,返回它的 后序 遍历。

题目解析

栈(Stack)的思路来处理问题。

后序遍历的顺序为左-右-根,具体算法为:

  • 先将根结点压入栈,然后定义一个辅助结点head
  • while循环的条件是栈不为空
  • 在循环中,首先将栈顶结点t取出来
  • 如果栈顶结点没有左右子结点,或者其左子结点是head,或者其右子结点是head的情况下。我们将栈顶结点值加入结果res中,并将栈顶元素移出栈,然后将head指向栈顶元素
  • 否则的话就看如果右子结点不为空,将其加入栈
  • 再看左子结点不为空的话,就加入栈

动画描述

二叉树的后序遍历

二叉树的后序遍历

代码实现

public class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<Integer>();
    if(root == null)
        return res;
    Stack<TreeNode> stack = new Stack<TreeNode>();
    stack.push(root);
    while(!stack.isEmpty()){
        TreeNode node = stack.pop();
        if(node.left != null) stack.push(node.left);//和传统先序遍历不一样,先将左结点入栈
        if(node.right != null) stack.push(node.right);//后将右结点入栈
        res.add(0,node.val);                        //逆序添加结点值
    }     
    return res;
   }
}

4. 二叉树的层序遍历

题目来源于 LeetCode 第 102 号问题:二叉树的层序遍历。

题目描述

给定一个二叉树,返回其按层次遍历的节点值。 (即逐层地,从左到右访问所有节点)。

例如:
给定二叉树: [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

返回其层次遍历结果:

```
[
[3],
[9,20],
[15,7]
]

top Created with Sketch.