算法类型题解 （三）——二叉树与二叉搜索树

前言

二叉树递归与迭代

二叉搜索树的最近公共祖先

题目

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]

思路

由二叉搜索树的性质，如果 p.val 和 q.val 都比 root.val 小，那么 p、q 肯定在 root 的左子树。
题规模就变小了，递归左子树就行。
如果 p.val 和 q.val 都比 root.val 大，则递归右子树。
其他情况，root 即为所求，不管是一个大于 root.val 一个小于 root.val，还是一个等于一个小于，还是一个等于一个大于。
为什么？
因为，只要不是 p 和 q 的值都大于（小于）root.val，即，不同处在 root 的一个子树中，就只有这三种情况：
p 和 q 分居 root 的左右子树。
root 就是 p，q 在 p 的子树中。
root 就是 q，p 在 q 的子树中
这三种情况，p 和 q 的公共祖先都是 root。

递归

var lowestCommonAncestor = function(root, p, q) {
    if(p.val<root.val&&q.val<root.val){
        return lowestCommonAncestor(root.left,p,q)
    };
    if(p.val>root.val&&q.val>root.val){
        return lowestCommonAncestor(root.right,p,q)
    }
    return root
};

迭代

const lowestCommonAncestor = (root, p, q) => {
  while (root) {
    if (p.val < root.val && q.val < root.val) {
      root = root.left;
    } else if (p.val > root.val && q.val > root.val) {
      root = root.right;
    } else {
      break;
    }
  }
  return root;
};

二叉树的后序遍历

题目

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

思路

先右节点再左节点
递归+dfs
迭代

// var postorderTraversal = function(root) {
//     let res=[]
//     function dfs(root,res){
//         if(root==null) return res
//         dfs(root.left,res)
//         dfs(root.right,res)
//         res.push(root.val)
//     }
//     dfs(root,res)
//     return res
// };
var postorderTraversal = function(root) {
    if(!root) return []
    let res=[root]
    let queue=[]
    while(res.length){
        let len=res.length
        let node=res.shift()||new TreeNode()
        if(node.left) res.unshift(node.left)
        if(node.right) res.unshift(node.right)
        queue.unshift(node.val)
        }
    return queue
};