114. Flatten Binary Tree to Linked List

Given a binary tree, flatten it to a linked list in-place.

For example,
Given

         1
        / \
       2   5
      / \   \
     3   4   6
//The flattened tree should look like:
   1
    \
     2
      \
       3
        \
         4
          \
           5
            \
             6

思路: 用Stack,如果当前节点有右子树,把右子树入栈,左子树放到右子树,如果找到左子树叶子节点,左子树叶子节点接到stack中pop出来的右子树节点。
复杂度: Time O(n), Space O(n)

public class Solution {
    public void flatten(TreeNode root) {
        if (root == null) return;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while(cur != null || !stack.isEmpty()) {
           if (cur.right != null) { // 右子树放到stack
               stack.push(cur.right);
           }
           if (cur.left != null) { // 如果右左子树,左子树变为右子树
               cur.right = cur.left;
               cur.left = null; // 原来左子树为null
           } else if (!stack.isEmpty()) { // 找到左子树的叶子
               TreeNode temp = stack.pop(); 
               cur.right = temp;
           }
           cur = cur.right;
        }
    }
}

235 Lowest Common Ancestor of a Binary Search Tree

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

思路: 用树的遍历方法来寻找,则LCA必然存在于1. p跟q中的一个 2. p,q所在的左右子树中.
复杂度: time O(n), space O(1)

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

270. Closest Binary Search Tree Value

Given a non-empty binary search tree and a target value, find the value in the BST that is closest to the target.

Note:
Given target value is a floating point.
You are guaranteed to have only one unique value in the BST that is closest to the target.

思路:用的pre-order travseral来做的,需要用一个global mindiff来找到target跟节点的最小差值,然后把此节点赋给closet.

public class Solution {
    public int closestValue(TreeNode root, double target) {
        int closet = root.val;
        double mindiff = Double.MAX_VALUE;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode current = root;
        while(!stack.isEmpty() || current != null) {
            if (current != null) {
                stack.push(current);
                double diff = Math.abs(target - current.val);
                if (diff < mindiff) {
                    mindiff = diff;
                    closet = current.val;
                }
                current = current.left;
            } else {
                current = stack.pop();
                current = current.right;
            }
        }

        return closet;
    }
}

二分, 递归

public class Solution {
    public int closestValue(TreeNode root, double target) {
        int closet = root.val;
        while(root != null) {
            // 更新到离目标节点的最近值
            closet = Math.abs(closet - target) > Math.abs(root.val - target) ? root.val : closet;
            root = target < root.val ? root.left : root.right; // 二分,找所在节点
        }
        return closet;
    }
}

Reference: https://segmentfault.com/a/1190000003797291