二叉树的遍历

Wu Jun 2019-12-25 15:59:03
Categories: > > Tags:

有两种通用的遍历树的策略:

    1
/ \
2   3
/ \   \
4   5   6

题目出处

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

1 前序遍历

1.1 递归解法

“自顶向下” 的解决方案

在每个递归层级,首先访问节点来计算一些值,并在递归调用函数时将这些值传递到子节点。

1. return specific value for null node
2. update the answer if needed                      // answer <-- params
3. left_ans = top_down(root.left, left_params)		// left_params <-- root.val, params
4. right_ans = top_down(root.right, right_params)	// right_params <-- root.val, params
5. return the answer if needed                      // answer <-- left_ans, right_ans
class Solution {
    public static void preorderTraversalRec(TreeNode root) {
        if (root == null) {
            return;
        }
        System.out.print(root.val + " ");
        preorderTraversalRec(root.left);
        preorderTraversalRec(root.right);
    }
}

1.2 迭代解法

用一个辅助栈,从根节点开始,每次迭代弹出当前栈顶元素,并将其孩子节点压入栈中,先压右孩子再压左孩子。

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();

        if (null == root) {
            return result;
        }

        Deque<TreeNode> stack = new ArrayDeque<>();
        stack.push(root);

        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            result.add(node.val);
            //FILO, push right first,can get left earlier
            if (null != node.right) {
                stack.push(node.right);
            }
            if (null != node.left) {
                stack.push(node.left);
            }
        }

        return result;
    }
}

1.3 相关试题

1)判断两棵二叉树是否相同

递归解法
迭代解法

前序遍历,对每个节点进行比较

2)自顶向下的最大深度

104. 二叉树的最大深度

class Solution {
    private int answer;        // don't forget to initialize answer before call maximum_depth

    private void maximum_depth(TreeNode root, int depth) {
        if (root == null) {
            return;
        }
        if (root.left == null && root.right == null) {
            answer = Math.max(answer, depth);
        }
        maximum_depth(root.left, depth + 1);
        maximum_depth(root.right, depth + 1);
    }
}

2 中序遍历

2.1 递归解法

中序遍历递归解法

class Solution {
    public static void inorderTraversalRec(TreeNode root) {
        if (root == null) {
            return;
        }
        inorderTraversalRec(root.left);
        System.out.print(root.val + " ");
        inorderTraversalRec(root.right);
    }
}

2.2 迭代解法

用栈先把根节点的所有左孩子都添加到栈内,然后输出栈顶元素,再处理栈顶元素的右子树

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if (null == root) {
            return list;
        }

        Deque<TreeNode> stack = new ArrayDeque<>();
        while (true) {
            //1. push all left nodes into stack
            while (null != root) {
                stack.push(root);
                root = root.left;
            }

            //2. get previous pushed node to continue
            //2.1 if empty, means finished
            if (stack.isEmpty()) {
                break;
            }
            //2.2 get one
            TreeNode node = stack.pop();

            //3. handle (left)middle
            list.add(node.val);

            //4. handle right
            root = node.right;
        }
        return list;
    }
}

3 后序遍历

3.1 递归解法

“自底向上” 的解决方案

在每个递归层次上,我们首先对所有子节点递归地调用函数,然后根据返回值和根节点本身的值得到答案。

1. return specific value for null node
2. left_ans = bottom_up(root.left)			// call function recursively for left child
3. right_ans = bottom_up(root.right)		// call function recursively for right child
4. return answers                           // answer <-- left_ans, right_ans, root.val
class Solution {
    public static void postorderTraversalRec(TreeNode root) {
        if (root == null) {
            return;
        }
        postorderTraversalRec(root.left);
        postorderTraversalRec(root.right);
        System.out.print(root.val + " ");
    }
}

3.2 迭代解法

后序遍历跟中序遍历很像,先遍历左边,判断中点时,先判断有没有右节点,有的话要先处理右边。

处理完右边会回到中点,中点还是有右节点,为了不陷入循环,需要记录下右节点是否处理过。

因为每个中点只关心一个右节点,并且这个右节点pop之后下一个pop的一定是对应的中点,所以只需要一个额外变量记录处理过的右节点。

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (null == root) {
            return result;
        }

        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode handledRight = null;
        while (true) {
            //1. push all left nodes into stack
            while (null != root) {
                stack.push(root);
                root = root.left;
            }

            //2. get previous pushed node to continue
            //2.1 if empty, means finished
            if (stack.isEmpty()) {
                break;
            }
            //2.2 get one
            TreeNode node = stack.pop();

            //3.1 if has right, current node is a middle node
            if (null != node.right && node.right != handledRight) {
                // if right hasn't been handled, push current middle note back to stack
                stack.push(node);
                // start to handle right
                root = node.right;
            } else {
                //3.2 if doesn't has right, or right has been handled, can handle middle node
                result.add(node.val);
                handledRight = node;
            }
        }

        return result;
    }
}

`

3.3 相关试题

1)自底向上的最大深度

104. 二叉树的最大深度

class Solution {
    public int maximum_depth(TreeNode root) {
        if (root == null) {
            return 0;                                   // return 0 for null node
        }
        int left_depth = maximum_depth(root.left);
        int right_depth = maximum_depth(root.right);
        return Math.max(left_depth, right_depth) + 1;    // return depth of the subtree rooted at root
    }
}

4 层序遍历

4.1 递归解法

很少有人会用递归去做 level traversal,基本思想是用一个大的 ArrayList,里面包含了每一层的 ArrayList。大的 ArrayList 的 size 和 level 有关系

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> levels = new ArrayList<>();
        if (null == root) {
            return levels;
        }
        dfs(root, 0, levels);
        return levels;
    }

    private static void dfs(TreeNode node, int level, List<List<Integer>> levels) {
        // 添加一个新的 ArrayList 表示新的一层
        if (level >= levels.size()) {
            levels.add(new ArrayList<Integer>());
        }

        // 把节点添加到当前这层的 ArrayList 里
        levels.get(level).add(node.val);

        // 递归处理下一层的左子树和右子树
        if (null != node.left) {
            dfs(node.left, level + 1, levels);
        }
        if (null != node.right) {
            dfs(node.right, level + 1, levels);
        }
    }
}

4.2 迭代解法

相当于广度优先搜索,使用队列实现。队列初始化,将根节点压入队列。当队列不为空,进行如下操作: 弹出一个节点 ,访问,若左子节点或右子节点不为空,将其压入队列

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> levels = new ArrayList<>();
        if (null == root) {
            return levels;
        }

        Deque<TreeNode> queue = new ArrayDeque<>();
        queue.addLast(root);
        //each loop, handle one level
        while (!queue.isEmpty()) {
            List<Integer> thisLevel = new ArrayList<>();
            //nodes in queue now if from one level 
            int thisLevelSize = queue.size();
            while (thisLevelSize-- > 0) {
                //fetch this level's node
                TreeNode node = queue.removeFirst();
                thisLevel.add(node.val);

                //add next level node into queue
                if (null != node.left) {
                    queue.addLast(node.left);
                }
                if (null != node.right) {
                    queue.addLast(node.right);
                }
            }
            levels.add(thisLevel);
        }
        return levels;
    }
}

4.3 相关试题

1)自底向上的层次遍历

在层次遍历的基础上,使返回的列表是倒序就行

class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        LinkedList<List<Integer>> result = new LinkedList<>();
        if (null == root) {
            return result;
        }

        ArrayDeque<TreeNode> queue = new ArrayDeque<>();
        int level = 0;
        queue.addLast(root);

        while (!queue.isEmpty()) {
            result.addFirst(new ArrayList<>());

            int levelSize = queue.size();
            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.removeFirst();
                result.get(0).add(node.val);
                if (null != node.left) {
                    queue.addLast(node.left);
                }
                if (null != node.right) {
                    queue.addLast(node.right);
                }
            }
            levelSize++;
        }

        return result;
    }
}

2)一棵树每层节点的平均数

问题:给定一个非空二叉树, 返回一个由每层节点平均值组成的数组.

思路:层序遍历,计算每层的平均值

class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> result = new ArrayList<>();
        if (null == root) {
            return result;
        }

        ArrayDeque<TreeNode> queue = new ArrayDeque<>();
        queue.addLast(root);

        while (!queue.isEmpty()) {
            int count = queue.size();
            double sum = 0;
            for (int i = 0; i < count; ++i) {
                TreeNode node = queue.removeFirst();

                sum += node.val;

                if (null != node.left) {
                    queue.addLast(node.left);
                }
                if (null != node.right) {
                    queue.addLast(node.right);
                }
            }
            result.add(sum / count);
        }

        return result;
    }
}

3)得到左下角的节点

问题:给定一个二叉树,在树的最后一行找到最左边的值。

思路:层序遍历,从右到左,遍历的最后一个节点就是左下角的节点

class Solution {
    public int findBottomLeftValue(TreeNode root) {
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            root = queue.poll();
            if (null != root.right) {
                queue.add(root.right);
            }
            if (null != root.left) {
                queue.add(root.left);
            }
        }
        return root.val;
    }
}

4)求二叉树中的节点个数

5)二叉树的最大深度

递归解法
class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }
}
迭代解法

层序遍历,每层加一

6)求二叉树第 K 层的节点个数

递归解法
class Solution {
    public static int getNodeNumKthLevelRec(TreeNode root, int k) {
        if (root == null || k < 1) {
            return 0;
        }

        if (k == 1) {
            return 1;
        }

        int numLeft = getNodeNumKthLevelRec(root.left, k - 1);
        int numRight = getNodeNumKthLevelRec(root.right, k - 1);
        return numLeft + numRight;
    }
}
迭代解法

层序遍历,到第 k 层时计数

7)求二叉树中叶子节点的个数

递归解法
class Solution {
    public int getNodeNumLeafRec(TreeNode root) {
        if (root == null) {
            return 0;
        }

        if (root.left == null && root.right == null) {
            return 1;
        }

        return getNodeNumLeafRec(root.left) + getNodeNumLeafRec(root.right);
    }
}
迭代解法

层序遍历,如果当前节点没有左右子树,则是叶子节点,计数加一

5 其它

自顶向下

101. 对称二叉树

递归
class Solution {
    public boolean isSymmetric(TreeNode root) {
        return isSymmetric(root, root);
    }

    private boolean isSymmetric(TreeNode left, TreeNode right) {
        if (left == null && right == null) {
            return true;
        } else if (left == null || right == null) {
            return false;
        } else if (left.val != right.val) {
            return false;
        } else {
            //每个树的右子树都与另一个树的左子树镜像对称
            return isSymmetric(left.left, right.right) && isSymmetric(right.left, left.right);
        }
    }
}
迭代

引入一个队列,把递归改写成迭代。

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

  public boolean isSymmetric(TreeNode left, TreeNode right) {
    Queue<TreeNode> queue = new LinkedList<TreeNode>();
    queue.offer(left);
    queue.offer(right);
    while(!queue.isEmpty()){
      TreeNode newLeft = queue.poll();
      TreeNode newRight = queue.poll();

      if(newLeft == null && newRight == null){
        continue;
      }

      if(newLeft == null || newRight == null){
        return false;
      }

      if(newLeft.val != newRight.val){
        return false;
      }

      queue.offer(newLeft.left);
      queue.offer(newRight.right);
      queue.offer(newLeft.right);
      queue.offer(newRight.left);
    }
    return true;
  }
}