按之字形打印二叉树

剑指offer：按之字形顺序打印二叉树

请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。

• 设两个栈，s2存放奇数层，s1存放偶数层
• 遍历s2节点的同时按照左子树、右子树的顺序加入s1，
• 遍历s1节点的同时按照右子树、左子树的顺序加入s2

import java.util.ArrayList;import java.util.Stack;/*public class TreeNode {    int val = 0;    TreeNode left = null;    TreeNode right = null;    public TreeNode(int val) {        this.val = val;    }}*/public class Solution {    public ArrayList > Print(TreeNode pRoot) {        ArrayList > res = new ArrayList >();        Stack s1 = new Stack();        Stack s2 = new Stack();        int flag = 1;        if(pRoot == null)            return res;        s2.push(pRoot);        ArrayList temp = new ArrayList();        while(!s1.isEmpty() || !s2.isEmpty()){            if(flag % 2 != 0){                while(!s2.isEmpty()){                    TreeNode node = s2.pop();                    temp.add(node.val);                    if(node.left != null){                        s1.push(node.left);                    }                    if(node.right != null){                        s1.push(node.right);                    }                }            }            if(flag % 2 == 0){                while(!s1.isEmpty()){                    TreeNode node = s1.pop();                    temp.add(node.val);                    if(node.right != null){                        s2.push(node.right);                    }                    if(node.left != null){                        s2.push(node.left);                    }                }            }            res.add(new ArrayList(temp));            temp.clear();            flag ++;        }        return res;    }}

前中后序遍历

    1   / \  2   3 / \   \4   5   6

• 层次遍历顺序：[1 2 3 4 5 6]
• 前序遍历顺序：[1 2 4 5 3 6]
• 中序遍历顺序：[4 2 5 1 3 6]
• 后序遍历顺序：[4 5 2 6 3 1]

层次遍历使用 BFS 实现，利用的就是 BFS 一层一层遍历的特性；而前序、中序、后序遍历利用了 DFS 实现。

前序、中序、后序遍只是在对节点访问的顺序有一点不同，其它都相同。

① 前序

void dfs(TreeNode root) {    visit(root);    dfs(root.left);    dfs(root.right);}

② 中序

void dfs(TreeNode root) {    dfs(root.left);    visit(root);    dfs(root.right);}

③ 后序

void dfs(TreeNode root) {    dfs(root.left);    dfs(root.right);    visit(root);}

1. 非递归实现二叉树的前序遍历

144. Binary Tree Preorder Traversal (Medium)

Leetcode / 力扣

public List preorderTraversal(TreeNode root) {    List ret = new ArrayList<>();    Stack stack = new Stack<>();    stack.push(root);    while (!stack.isEmpty()) {        TreeNode node = stack.pop();        if (node == null) continue;        ret.add(node.val);        stack.push(node.right);  // 先右后左，保证左子树先遍历        stack.push(node.left);    }    return ret;}

2. 非递归实现二叉树的后序遍历

145. Binary Tree Postorder Traversal (Medium)

Leetcode / 力扣

前序遍历为 root -> left -> right，后序遍历为 left -> right -> root。可以修改前序遍历成为 root -> right -> left，那么这个顺序就和后序遍历正好相反。

public List postorderTraversal(TreeNode root) {    List ret = new ArrayList<>();    Stack stack = new Stack<>();    stack.push(root);    while (!stack.isEmpty()) {        TreeNode node = stack.pop();        if (node == null) continue;        ret.add(node.val);        stack.push(node.left);        stack.push(node.right);    }    Collections.reverse(ret);    return ret;}

3. 非递归实现二叉树的中序遍历

94. Binary Tree Inorder Traversal (Medium)

Leetcode / 力扣

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

BST

二叉查找树（BST）：根节点大于等于左子树所有节点，小于等于右子树所有节点。

二叉查找树中序遍历有序。

1. 修剪二叉查找树

669. Trim a Binary Search Tree (Easy)

Leetcode / 力扣

Input:    3   / \  0   4   \    2   /  1  L = 1  R = 3Output:      3     /   2  / 1

题目描述：只保留值在 L ~ R 之间的节点

public TreeNode trimBST(TreeNode root, int L, int R) {    if (root == null) return null;    if (root.val > R) return trimBST(root.left, L, R);    if (root.val < L) return trimBST(root.right, L, R);    root.left = trimBST(root.left, L, R);    root.right = trimBST(root.right, L, R);    return root;}

2. 寻找二叉查找树的第 k 个元素

230. Kth Smallest Element in a BST (Medium)

Leetcode / 力扣

中序遍历解法：

private int cnt = 0;private int val;public int kthSmallest(TreeNode root, int k) {    inOrder(root, k);    return val;}private void inOrder(TreeNode node, int k) {    if (node == null) return;    inOrder(node.left, k);    cnt++;    if (cnt == k) {        val = node.val;        return;    }    inOrder(node.right, k);}

递归解法：

public int kthSmallest(TreeNode root, int k) {    int leftCnt = count(root.left);    if (leftCnt == k - 1) return root.val;    if (leftCnt > k - 1) return kthSmallest(root.left, k);    return kthSmallest(root.right, k - leftCnt - 1);}private int count(TreeNode node) {    if (node == null) return 0;    return 1 + count(node.left) + count(node.right);}

3. 把二叉查找树每个节点的值都加上比它大的节点的值

Convert BST to Greater Tree (Easy)

Leetcode / 力扣

Input: The root of a Binary Search Tree like this:              5            /   \           2     13Output: The root of a Greater Tree like this:             18            /   \          20     13

先遍历右子树。

private int sum = 0;public TreeNode convertBST(TreeNode root) {    traver(root);    return root;}private void traver(TreeNode node) {    if (node == null) return;    traver(node.right);    sum += node.val;    node.val = sum;    traver(node.left);}

4. 二叉查找树的最近公共祖先

235. Lowest Common Ancestor of a Binary Search Tree (Easy)

Leetcode / 力扣

        _______6______      /                \  ___2__             ___8__ /      \           /      \0        4         7        9        /  \       3   5For example, the lowest common ancestor (LCA) of nodes 2 and 8 is 6. Another example is LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {    if (root.val > p.val && root.val > q.val) return lowestCommonAncestor(root.left, p, q);    if (root.val < p.val && root.val < q.val) return lowestCommonAncestor(root.right, p, q);    return root;}

5. 二叉树的最近公共祖先

236. Lowest Common Ancestor of a Binary Tree (Medium)

Leetcode / 力扣

       _______3______      /              \  ___5__           ___1__ /      \         /      \6        2       0        8        /  \       7    4For example, the lowest common ancestor (LCA) of nodes 5 and 1 is 3. Another example is LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {    if (root == null || root == p || root == q) return root;    TreeNode left = lowestCommonAncestor(root.left, p, q);    TreeNode right = lowestCommonAncestor(root.right, p, q);    return left == null ? right : right == null ? left : root;}

6. 从有序数组中构造二叉查找树

108. Convert Sorted Array to Binary Search Tree (Easy)

Leetcode / 力扣

public TreeNode sortedArrayToBST(int[] nums) {    return toBST(nums, 0, nums.length - 1);}private TreeNode toBST(int[] nums, int sIdx, int eIdx){    if (sIdx > eIdx) return null;    int mIdx = (sIdx + eIdx) / 2;    TreeNode root = new TreeNode(nums[mIdx]);    root.left =  toBST(nums, sIdx, mIdx - 1);    root.right = toBST(nums, mIdx + 1, eIdx);    return root;}

7. 根据有序链表构造平衡的二叉查找树

109. Convert Sorted List to Binary Search Tree (Medium)

Leetcode / 力扣

Given the sorted linked list: [-10,-3,0,5,9],One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:      0     / \   -3   9   /   / -10  5

public TreeNode sortedListToBST(ListNode head) {    if (head == null) return null;    if (head.next == null) return new TreeNode(head.val);    ListNode preMid = preMid(head);    ListNode mid = preMid.next;    preMid.next = null;  // 断开链表    TreeNode t = new TreeNode(mid.val);    t.left = sortedListToBST(head);    t.right = sortedListToBST(mid.next);    return t;}private ListNode preMid(ListNode head) {    ListNode slow = head, fast = head.next;    ListNode pre = head;    while (fast != null && fast.next != null) {        pre = slow;        slow = slow.next;        fast = fast.next.next;    }    return pre;}

8. 在二叉查找树中寻找两个节点，使它们的和为一个给定值

653. Two Sum IV - Input is a BST (Easy)

Leetcode / 力扣

Input:    5   / \  3   6 / \   \2   4   7Target = 9Output: True

使用中序遍历得到有序数组之后，再利用双指针对数组进行查找。

应该注意到，这一题不能用分别在左右子树两部分来处理这种思想，因为两个待求的节点可能分别在左右子树中。

public boolean findTarget(TreeNode root, int k) {    List nums = new ArrayList<>();    inOrder(root, nums);    int i = 0, j = nums.size() - 1;    while (i < j) {        int sum = nums.get(i) + nums.get(j);        if (sum == k) return true;        if (sum < k) i++;        else j--;    }    return false;}private void inOrder(TreeNode root, List nums) {    if (root == null) return;    inOrder(root.left, nums);    nums.add(root.val);    inOrder(root.right, nums);}

9. 在二叉查找树中查找两个节点之差的最小绝对值

530. Minimum Absolute Difference in BST (Easy)

Leetcode / 力扣

Input:   1    \     3    /   2Output:1

利用二叉查找树的中序遍历为有序的性质，计算中序遍历中临近的两个节点之差的绝对值，取最小值。

private int minDiff = Integer.MAX_VALUE;private TreeNode preNode = null;public int getMinimumDifference(TreeNode root) {    inOrder(root);    return minDiff;}private void inOrder(TreeNode node) {    if (node == null) return;    inOrder(node.left);    if (preNode != null) minDiff = Math.min(minDiff, node.val - preNode.val);    preNode = node;    inOrder(node.right);}

10. 寻找二叉查找树中出现次数最多的值

501. Find Mode in Binary Search Tree (Easy)

Leetcode / 力扣

   1    \     2    /   2return [2].

答案可能不止一个，也就是有多个值出现的次数一样多。

private int curCnt = 1;private int maxCnt = 1;private TreeNode preNode = null;public int[] findMode(TreeNode root) {    List maxCntNums = new ArrayList<>();    inOrder(root, maxCntNums);    int[] ret = new int[maxCntNums.size()];    int idx = 0;    for (int num : maxCntNums) {        ret[idx++] = num;    }    return ret;}private void inOrder(TreeNode node, List nums) {    if (node == null) return;    inOrder(node.left, nums);    if (preNode != null) {        if (preNode.val == node.val) curCnt++;        else curCnt = 1;    }    if (curCnt > maxCnt) {        maxCnt = curCnt;        nums.clear();        nums.add(node.val);    } else if (curCnt == maxCnt) {        nums.add(node.val);    }    preNode = node;    inOrder(node.right, nums);}

参考文章

Leetcode 题解 - 树

小结

如果你想学好算法，建议上面二叉树的题目都刷一下。如果你只是想应付面试，主要看一下高频的面试题目即可。

• 树的递归。比如树的深度，最小深度，树的镜像。
• 二叉树的前序遍历，中序遍历，后续遍历，记住，递归和非递归解法都要会。学会举一反三。
• 二叉树的层序遍历，递归和非递归也都要会。
• 常见的 BST 算法。二叉查找树的最近公共祖先（两个元素的，三个元素的，多个元素呢）。二叉树的最近公共祖先。

如果你觉得对你有所帮助，请帮忙 start
Android_interview github。或者关注我的微信公众号徐公码字

更多相关文章

1. 我的android 第10天 - pull解析Xml文档
2. [置顶] Android曙光集群发来的邀请函
3. (一)Android数据结构学习之链表
4. Android(安卓)APP UI卡顿的原理
5. android程序获取WIFI的IP地址和MAC地址
6. Android(安卓)Content Provider详解及示例代码
7. android实现上下滑动
8. Android(安卓)节点进度条
9. PULL解析XML

随机推荐

1. Android访问资源
2. Android(安卓)studio 3.1.2 开发环境搭建
3. Android(安卓)字体设置-Typeface讲解
4. AS Gradle构建工具与Android(安卓)plugin
5. GitHub上优秀Android(安卓)UI Library
6. Android(安卓)studio之蓝牙
7. Android(安卓)- 电话拦截
8. Mac环境下交叉编译生成Android版本的Assi
9. android存储方式（转）
10. Android根据屏幕宽度，按比例缩放图片