递归形式遍历二叉树

  1.     // 前序遍历
  2.     public static void preOrderRecur(Node head) {
  3.         if (head == null) {
  4.             return;
  5.         }
  6.         System.out.print(head.value + " ");
  7.         preOrderRecur(head.left);
  8.         preOrderRecur(head.right);
  9.     }
  10.     // 中序遍历
  11.     public static void inOrderRecur(Node head) {
  12.         if (head == null) {
  13.             return;
  14.         }
  15.         inOrderRecur(head.left);
  16.         System.out.print(head.value + " ");
  17.         inOrderRecur(head.right);
  18.     }
  19.     // 后续遍历
  20.     public static void posOrderRecur(Node head) {
  21.         if (head == null) {
  22.             return;
  23.         }
  24.         posOrderRecur(head.left);
  25.         posOrderRecur(head.right);
  26.         System.out.print(head.value + " ");
  27.     }

非递归遍历

  1.     public static void preOrderUnRecur(Node head) {
  2.         System.out.print("pre-order: ");
  3.         if (head != null) {
  4.             Stack<Node> stack = new Stack<Node>();
  5.             stack.add(head);
  6.             while (!stack.isEmpty()) {
  7.                 head = stack.pop();
  8.                 System.out.print(head.value + " ");
  9.                 if (head.right != null) {
  10.                     stack.push(head.right);
  11.                 }
  12.                 if (head.left != null) {
  13.                     stack.push(head.left);
  14.                 }
  15.             }
  16.         }
  17.         System.out.println();
  18.     }
  20.     public static void inOrderUnRecur(Node head) {
  21.         System.out.print("in-order: ");
  22.         if (head != null) {
  23.             Stack<Node> stack = new Stack<Node>();
  24.             while (!stack.isEmpty() || head != null) {
  25.                 if (head != null) {
  26.                     stack.push(head);
  27.                     head = head.left;
  28.                 } else {
  29.                     head = stack.pop();
  30.                     System.out.print(head.value + " ");
  31.                     head = head.right;
  32.                 }
  33.             }
  34.         }
  35.         System.out.println();
  36.     }
  37.     // 非递归-后序遍历双栈法
  38.     public static void posOrderUnRecur1(Node head) {
  39.         System.out.print("pos-order: ");
  40.         if (head != null) {
  41.             Stack<Node> s1 = new Stack<Node>();
  42.             Stack<Node> s2 = new Stack<Node>();
  43.             s1.push(head);
  44.             while (!s1.isEmpty()) {
  45.                 head = s1.pop();
  46.                 s2.push(head);
  47.                 if (head.left != null) {
  48.                     s1.push(head.left);
  49.                 }
  50.                 if (head.right != null) {
  51.                     s1.push(head.right);
  52.                 }
  53.             }
  54.             while (!s2.isEmpty()) {
  55.                 System.out.print(s2.pop().value + " ");
  56.             }
  57.         }
  58.         System.out.println();
  59.     }
  60.     // 非递归-单栈法
  61.     public static void posOrderUnRecur2(Node h) {
  62.         System.out.print("pos-order: ");
  63.         if (h != null) {
  64.             Stack<Node> stack = new Stack<Node>();
  65.             stack.push(h);
  66.             Node c = null;
  67.             while (!stack.isEmpty()) {
  68.                 c = stack.peek();
  69.                 if (c.left != null && h != c.left && h != c.right) {
  70.                     stack.push(c.left);
  71.                 } else if (c.right != null && h != c.right) {
  72.                     stack.push(c.right);
  73.                 } else {
  74.                     System.out.print(stack.pop().value + " ");
  75.                     h = c;
  76.                 }
  77.             }
  78.         }
  79.         System.out.println();
  80.     }

格式统一非递归遍历

// 前序遍历 跟左右
public void preorderTraversal(TreeNode root) {
    Stack<TreeNode> stack = new Stack<>();
    List<Integer> res = new ArrayList<>();
    while (root != null || !stack.isEmpty()) {
        // go left down to the ground
        while (root != null) {
            res.add(root.val);
            stack.push(root);
            root = root.left;
        }
        root = stack.pop();
        root = root.right;
    }
}


// 中序遍历  左根右
public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    while (root != null || !stack.isEmpty()) {
        while (root != null) {
            stack.push(root);
            root = root.left;
        }
        root = stack.pop();
        res.add(root.val);
        root = root.right;
    }
    return res;
}


// 后序遍历  左右跟，可以先通过根右左，然后反转成左右根
public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    while (root != null || !stack.isEmpty()) {
        while (root != null) {
            res.add(root.val);
            stack.push(root);
            root = root.right;
        }
        root = stack.pop();
        root = cur.left;
    }
    Collections.reverse(res);
    return res;
}

打印二叉树

    public static void printTree(Node head) {
        System.out.println("Binary Tree:");
        printInOrder(head, 0, "H", 17);
        System.out.println();
    }

    public static void printInOrder(Node head, int height, String to, int len) {
        if (head == null) {
            return;
        }
        printInOrder(head.right, height + 1, "v", len);
        String val = to + head.value + to;
        int lenM = val.length();
        int lenL = (len - lenM) / 2;
        int lenR = len - lenM - lenL;
        val = getSpace(lenL) + val + getSpace(lenR);
        System.out.println(getSpace(height * len) + val);
        printInOrder(head.left, height + 1, "^", len);
    }

    public static String getSpace(int num) {
        String space = " ";
        StringBuffer buf = new StringBuffer("");
        for (int i = 0; i < num; i++) {
            buf.append(space);
        }
        return buf.toString();
    }

宽度遍历

public static void w(Node head) {
    if (head == null) return;
    Queue<Node> queue = new LinkedList<>();
    queue.add(head);
    while(!queue.isEmpty()) {
        Node cur = queue.poll();
        System.out.println(cur.value);
        if (cur.left != null) {
            queue.add(cur.left);
        }    
        if (cur.right != null) {
            queue.add(cur.right);
        }    
    }    
}

二叉树的相关概念及其实现判断

  1. 如何判断一颗二叉树是否是搜索二叉树？

    若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
    image.png

     public static int preValue = Integer.MIN_VALUE;
 public static boolean isBST(Node head) {
     if (head == null) return true;
     boolean isLeftBST = isBST(head.left);

     if (!isLeftBST) return false;

     if (head.value <= preValue) {
         return false;
     } else {
         preValue = head.value;
     }
     return isBST(head.right);

 }

  2. 如何判断一颗二叉树是完全二叉树？

     public static boolean isCBT(Node head) {
     if (head == null) {
         return true;
     }
     LinkedList<Node> queue = new LinkedList<>();
     boolean leaf = false;
     Node l = null;
     Node r = null;
     queue.add(head);
     while (!queue.isEmpty()) {
         head = queue.poll();
         l = head.left;
         r = head.right;
         if ((leaf && (l != null || r != null)) || (l == null && r != null)) {
             return false;
         }
         if (l != null) {
             queue.add(l);
         }
         if (r != null) {
             queue.add(r);
         } else {
             leaf = true;
         }
     }
     return true;
 }

  3. 如何判断一颗二叉树是否是满二叉树？

  4. 如何判断一颗二叉树是否是平衡二叉树？

平衡树(Balance Tree，BT) 指的是，任意节点的子树的高度差都小于等于1。

    public static boolean isBalanced(Node head) {
        return process(head).isBalanced;
    }

    public static class ReturnType {
        public boolean isBalanced;
        public int height;

        public ReturnType(boolean isB, int hei) {
            isBalanced = isB;
            height = hei;
        }
    }

    public static ReturnType process(Node x) {
        if (x == null) {
            return new ReturnType(true, 0);
        }
        ReturnType leftData = process(x.left);
        ReturnType rightData = process(x.right);
        int height = Math.max(leftData.height, rightData.height);
        boolean isBalanced = leftData.isBalanced && rightData.isBalanced
                && Math.abs(leftData.height - rightData.height) < 2;
        return new ReturnType(isBalanced, height);
    }

多练习树型DP的题

只要可以通过向左树要信息，向右树要信息，可以解决问题的题都可以利用上面的套路

给定两个二叉树的节点node1和node2，找到他们的最低公共祖先节点

    public static Node lowestAncestor(Node head, Node o1, Node o2) {
        if (head == null || head == o1 || head == o2) {
            return head;
        }
        Node left = lowestAncestor(head.left, o1, o2);
        Node right = lowestAncestor(head.right, o1, o2);
        if (left != null && right != null) {
            return head;
        }
        return left != null ? left : right;
    }

在二叉树中找到一个节点的后继节点

【题目】现在有一种新的二叉树节点类型如下：

public class Node {
    public int value;
    public Node left;
    public Node right;
    public Node parent;
    public Node (int val) {
        value = val;
    }    
}

该结构比普通二叉树节点结构多了一个指向父节点的parent指针。
假设有一棵Node类型的节点组成的二叉树，树中每个节点的parent指针都正确地指向自己的父节点，头节点的parent指向null。
只给一个在二叉树中的某个节点node，请实现返回node的后继节点的函数。
在二叉树的中序遍历的序列中，node的下一个节点叫作node的后继节点。

    public static Node getSuccessorNode(Node node) {
        if (node == null) {
            return node;
        }
        if (node.right != null) {
            return getLeftMost(node.right);
        } else {
            Node parent = node.parent;
            while (parent != null && parent.left != node) {
                node = parent;
                parent = node.parent;
            }
            return parent;
        }
    }

    public static Node getLeftMost(Node node) {
        if (node == null) {
            return node;
        }
        while (node.left != null) {
            node = node.left;
        }
        return node;
    }

给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

  1. 递归

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

  2. BFS

    class Solution {
 public int maxDepth(TreeNode root) {
     if (root == null) {
         return 0;
     }
     int level = 0;
     Queue<TreeNode> queue = new LinkedList<TreeNode>();
     queue.add(root);
     while (!queue.isEmpty()) {
         int size = queue.size();
         level++;
         for (int i = 0; i < size; i++) {
             TreeNode node = queue.remove();
             if (node.left != null) queue.add(node.left);
             if (node.right != null) queue.add(node.right);
         }
     }
     return level;
 }
}

  3. DFS

    class Solution {
 int maxLevel = 0;

 public int maxDepth(TreeNode root) {
     if (root == null) {
         return 0;
     }
     dfs(root, 1);
     return maxLevel;
 }

 public void dfs(TreeNode root, int level) {
     if (root == null)
         return;
     if (level > maxLevel) maxLevel = level;
     dfs(root.left, level + 1);
     dfs(root.right, level + 1);
 }
}